欢迎来到
银狐的个人博客

C语言督学营 中期笔记 (Day3~4)


一研为定,万山无阻

文章目录 第四次 直播 单链表的头插与尾插顺序表的定义顺序表的增删改查头插法尾插法单链表的查找按序号查找按值查找 单链表的操作

第四次 直播 单链表的头插与尾插 使用C++ 的引用进行读写数据

顺序表的定义

顺序表

1、插入和删除操作移动大量元素。 2、数组的大小不好确定 3、占用一大段连续的存储空间,造成很多碎片。

单链表:逻辑上相邻的元素在物理上不相邻

LinkList 等价于 struct LNode *

头指针:链表中第一个结点的存储位置,用来标识单链表。头结点:在单链表第一个结点之前附加的一个结点,为了操作上的方便 顺序表的增删改查

 #include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElemType;//静态分配typedef struct{ElemType data[MaxSize];int length;//当前顺序表中有多少个元素}SqList;//动态分配#define InitSize 100typedef struct{ElemType *data;int capacity;//动态数组的最大容量int length;}SeqList;//i代表插入的位置,从1开始,e要插入的元素bool ListInsert(SqList &L,int i,EleC语言督学营 中期笔记 (Day3~4) 第1张图片-银狐博客mType e){if(i<1||i>L.length+1)//判断要插入的位置是否合法return false;if(L.length>=MaxSize)//超出空间了return false;for(int j=L.length;j>=i;j--)//移动顺序表中的元素L.data[j]=L.data[j-1];L.data[i-1]=e;//数组下标从零开始,插入第一个位置,访问的下标为0L.length++;return true;}//删除使用元素e的引用的目的是拿出对应的值bool ListDelete(SqList &L,int i,ElemType &e){if(i<1||i>L.length)//如果删除的位置是不合法return false;e=L.data[i-1];//获取顺序表中对应的元素,赋值给efor(int j=i;j<L.length;j++)L.data[j-1]=L.data[j];L.length--;//删除一个元素,顺序表长度减1return true;}//查找成功,返回位置,位置从1开始,查找失败,返回0int LocateElem(SqList L,ElemType e){int i;for(i=0;i<L.length;i++)if(L.data[i]==e)return i+1;//加1就是元素在顺序表中的位置return 0;}//打印顺序表元素void PrintList(SqList &L){for(int i=0;i<L.length;i++){printf("%4d",L.data[i]);}printf("\\n");}int main(){SqList L;//顺序表的名称bool ret;//查看返回值,布尔型是True,或者FalseElemType del;//要删除的元素//首先手动在顺序表中赋值L.data[0]=1;L.data[1]=2;L.data[2]=3;L.length=3;//总计三个元素ret=ListInsert(L,2,60);if(ret){printf("插入成功\\n");PrintList(L);}else{printf("插入失败\\n");}ret=ListDelete(L,1,del);if(ret){printf("删除成功\\n");printf("删除元素值为 %d\\n",del);PrintList(L);}else{printf("删除失败\\n");}ret=LocateElem(L,60);if(ret){printf("查找成功\\n");printf("元素位置为 %d\\n",ret);}else{printf("查找失败\\n");}system("pause");//停在控制台窗口}

头插法 使用头插法新建链表

LinkList CreatList1(LinkList &L)/C语言督学营 中期笔记 (Day3~4) 第2张图片-银狐博客/list_head_insert{LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));//带头结点的链表L->next=NULL;//L->data里边没放东西scanf("%d",&x);//从标准输入读取数据//3 4 5 6 7 9999while(x!=9999){s=(LNode*)malloc(sizeof(LNode));//申请一个新空间给s,强制类型转换s->data=x;//把读取到的值,给新空间中的data成员s->next=L->next;//让新结点的next指针指向链表的第一个元素(第一个放我们数据的元素)L->next=s;//让s作为第一个元素scanf("%d",&x);//读取标准输入}return L;}

尾插法 使用尾插法尾插法新建链表

LinkList CreatList2(LinkList &L)//list_tail_insert{int x;L=(LinkList)malloc(sizeof(LNode));//带头节点的链表LNode* s, * r = L;//LinkList s,r=L;也可以,r代表链表表尾结点,指向链表尾部//3 4 5 6 7 9999scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;//让尾部结点指向新结点r=s;//r指向新的表尾结点scanf("%d",&x);}r->next=NULL;//尾结点的next指针赋值为NULLreturn L;}

Tips: next指针,没有赋值为NULL造成的

单链表的查找 关于 q->next = p->next ; 的理解, -> 是指针访问成员变量(地址)p->next整体访问结构体空间里的一个成员 按序号查找

关键代码如下(伪代码)注意特殊情况(边界值的考虑)

LNode  *p = L->next ;int j = 1 ;while(P&&j<i){   p=p->next ;   j++ ;}return p ;

按值查找

关键代码如下(伪代码)注意特殊情况(边界值的考虑)

LNode  *p = L->next ;while( P!= NULL && p->data != e){    p=p->next ;}return p ;

单链表的操作

#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;//指向下一个结点 }LNode,*LinkList;//头插法新建链表LinkList CreatList1(LinkList &L)//list_head_insert{LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));//带头结点的链表L->next=NULL;//L->data里边没放东西scanf("%d",&x);//从标准输入读取数据//3 4 5 6 7 9999while(x!=9999){s=(LNode*)malloc(sizeof(LNode));//申请一个新空间给s,强制类型转换s->data=x;//把读取到的值,给新空间中的data成员s->next=L->next;//让新结点的next指针指向链表的第一个元素(第一个放我们数据的元素)L->next=s;//让s作为第一个元素scanf("%d",&x);//读取标准输入}return L;}//尾插法新建链表LinkList CreatList2(LinkList &L)//list_tail_insert{int x;L=(LinkList)malloc(sizeof(LNode));//带头节点的链表LNode* s, * r = L;//LinkList s,r=L;也可以,r代表链表表尾结点,指向链表尾部//3 4 5 6 7 9999scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;//让尾部结点指向新结点r=s;//r指向新的表尾结点scanf("%d",&x);}r->next=NULL;//尾结点的next指针赋值为NULLreturn L;}//按序号查找结点值LNode *GetElem(LinkList L,int i){int j=1;LNode *p=L->next;if(i==0)return L;if(i<1)return NULL;while(p&&j<i){p=p->next;j++;}return p;}//按值查找LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e)p=p->next;return p;}//新结点插入第i个位置bool ListFrontInsert(LinkList L,int i,ElemType e){LinkList p=GetElem(L,i-1);if(NULL==p){return false;}LinkList s=(LNode*)malloc(sizeof(LNode));//为新插入的结点申请空间s->data=e;s->next=p->next;p->next=s;return true;}//删除第i个结点bool ListDelete(LinkList L,int i){LinkList p=GetElem(L,i-1);if(NULL==p){return false;}LinkList q;q=p->next;p->next=q->next;//断链free(q);//释放对应结点的空间return true;}//打印链表中每个结点的值void PrintList(LinkList L){L=L->next;while(L!=NULL)//NULL是为了代表一张空的藏宝图{printf("%3d",L->data);//打印当前结点数据L=L->next;//指向下一个结点}printf("\\n");} //2.3 线性表的链式表示int main(){LinkList L;//链表头,是结构体指针类型LinkList search;//用来存储拿到的某一个节点//CreatList1(L);//输入数据可以为3 4 5 6 7 9999,头插法新建链表CreatList2(L);//输入数据可以为3 4 5 6 7 9999PrintList(L);//链表打印//search=GetElem(L,2);//if(search!=NULL)//{//printf("按序号查找成功\\n");//printf("%d\\n",search->data);//}//search=LocateElem(L,6);//按值查询//if(search!=NULL)//{//printf("按值查找成功\\n");//printf("%d\\n",search->data);//}//ListFrontInsert(L,2,99);//新结点插入第i个位置//PrintList(L);//ListDelete(L,4);//删除第4个结点//PrintList(L);}
赞(0) 打赏
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《C语言督学营 中期笔记 (Day3~4)》
文章链接:https://www.yinhu3.com/2492.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。
如果文章侵犯到你的权益,请查看本站免责声明:《免责声明》

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

愿意请我喝杯矿泉水吗

支付宝扫一扫打赏