资源描述：
《数据结构CH2-2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针存储其前驱或后继的存储单元地址每个结点，除存储本身信息外，还需额外空间存储其逻辑关系2.3.1单链表2.3.2双向链表2.3.3循环链表2.3.4静态链表2.3.1单链表定义：结点中只含一个指向后继的指针域的链表叫~例线性表(a1,a2,a3,a4,a5,a6,a7,a8)200190150NULL210260110数据域指针域160head头指针240存储地址110150160190200210240260a5a2a1a3a6a4a8a7datanext实现：typedefstructnode{e
2、lemtypedata;structnode*next;}linklist;数据域指针域结点a1a2a3a4a5a6a7a8^La1a2a3a4a5a6a7a8^LLa1a2an^……L空表∧L空表∧头结点第一个结点1、初始化单链表初始化一个带头结点的单链表linklist*InitList(linklist*L){L=(linklistn*)malloc(sizeof(linklist));L->next=NULL;returnL;}L空表∧2、建立单链表（1）在链表的头部插入结点建立单链表例：线性表（25，45，18，76）25∧H->next∧H->next25∧45H-
3、>next25∧4518H->next25∧451876H->next建立一个空表；读入一个数据元素值；while（未结束）{申请一个新结点空间；xss->next=H;H=s;将数据元素值填入新申请的结点空间中；读入下一个数据元素值；}将该结点插入到链表的头部；Hb……算法思想：//在链表的头部插入结点建立单链表linklist*createlist(){linklist*L=NULL,*s;intx;L=(linklist*)malloc(sizeof(linklist));L->next=NULL;scanf("%d",&x);while(x!=0){s=(linklis
4、t*)malloc(sizeof(linklist));s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);}return(L);}（2）在链表的尾部插入结点建立单链表例：线性表（25，45，18，76）∧H->next76∧184525rH->next45∧25rH->next18∧4525rH->next25∧rH->nextr建立一个空表,头指针为L；设置尾指针r指向头结点;读入一个数据元素值；while（未结束）{申请一个新结点空间,将数据元素值填入；算法描述修改尾指针;读入下一个数据元素值；}将该结点插入到尾指针r的后
5、面；算法思想：//不带头结点的单链表创建linklist*Creatlist2(){linklist*L=NULL;linklist*s,*r=NULL;intx;scanf("%d",&x);while(x!=0){s=(linklist*)malloc(sizeof(linklist));s->data=x;if(L==NULL)L=s;elser->next=s;r=s;scanf("%d",&x);}return(L);}//带头结点的单链表创建linklist*creat_LinkList2(){linklist*L;linklist*s,*r;intx;L=(lin
6、klist*)malloc(sizeof(linklist));L->next=NULL;r=L;scanf("%d",&x);while(x!=0){s=(linklist*)malloc(sizeof(linklist));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;return(L);}3、求表长算法思想：设置一个计数器j，初值为0；设置一个指针p，从第一个结点开始扫描；while（未结束）{j++;扫描下一个结点；}//带头结点的求表长算法intLenlist(linklist*L){linklist*p=L
7、->next;intj=0;while(p!=NULL){j++;p=p->next;}return(j);}//带头结点的求表长算法intLenlist(linklist*L){linklist*p=L;intj=0;while(p->next=NULL){j++;p=p->next;}return(j);}（1）按序号查找：linklist*GetItem(linklist*L,inti)算法思想：设置一个计数器j，初值为0；设置一个指针p，从第一个结点开始扫描；while（未结束&&不
