c语言之链表编程

《c语言之链表编程》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2.1试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。头指针：存放链表首地址的指针变量。头结点：链表的开始结点之前的一个同类型结点。开始结点：链表的第一个元素所在的结点。头指针的作用：用于确定链表的地址。头结点的作用：方便于处理开始结点的操作和处理其它结点的操作保持一致，也方便于处理空表的操作和处理非空表的操作保持一致。2.2有哪些链表可由一个尾指针来唯一确定？即从尾指针出发能访问链表上任何一个结点。单循环链表，双链表，双循环链表2.3设线性表存放在向量A[airsize]的前elenum个分量屮，且递增有序。试写一算法，将x插入到

2、线性表的适当位置上，以保持线性表的冇序性。并且分析算法的时间复杂度。#dcfincaiTsizc100intInsertOrder(intA[],intelenum,intx){inti=elenum-l;if(elenum==arrsize)〃在顺序表上进行插入操作必须先判满{printf("full”)；return0;}while(i>=0&&A[iJ>x){A[i+l]=A[i];i・・；}〃从后往前进行比较，比较的同时完成移动A[i+l]=x;elenum++;returnelenum;//返回变化之后的表长}〃本题也可以先进行比较，比较的

3、结果就是找到了插入的合适位置，然后再完成插入操作。但这样做比较耗时。假设n=elenum,则时间复杂度：最坏O(n),最好O⑴,平均O(n)2.4用向量作存储结构，试设计一个算法，仅用一个辅助结点，实现将线性表屮的结点循环右移k位的运算，并且分析算法的时间复杂度。voidMovcKList(inta[],intn,intk){inti,j,temp;for(i=l;i<=k;i++)〃外层for循环控制循坏右移的次数i{temp=a[n-l];〃把表尾元索保存到辅助结点变量temp中for(j=n-2;j>=0;j-)a[j+l]=a[j]；〃内层f

4、or循环完成一次整体右移一位aL0J=temp;〃把原來的表尾元素移至表头时间复杂度T(n)=k*n=0(n)2.5已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插入表L中，使L仍然有序。typcdcfintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;//linklist结构体类型描述voidInsertListOrder(linklist*L,datetypex){linklist*p=L;〃对寻位指针p初始化linklist*

5、s=(linklist*)malloc(sizeof(linklist));〃使用强制类型转换将新结点的地址赋给指针ss->data=x;while((p->next)&&(p->next->datancxt;〃后移寻位指针s->ncxt=p->ncxt;p->next=s;}〃本题也可以采用两个寻位指针p和q,让q始终跟随p的后移而后移。2.6设计一算法，逆置带头结点的动态单链表L。typcdcfintdatatype;typedefstructnode{datatypedata;structnode水next;}linklist

6、;voidRcvcrsc(linklist*L){linklist*p,*q;p=L->next;q=L->next;L->next=NULL;whilc(q){q=q->next;p->next=L->next;L->next=p;p=q；})〃用指针q遍历结点，指针p跟随指针q,使用头插法把当前结点*p插入到修改之后的单链表中。2.7试编写在带头结点的动态单链表和静态单链表上实现线性表操作Lcngth(L)的算法，并将长度写入头结点的数据域中。(1)typedefintdatatype;typedefstructnode{datatypedata

7、;structnode*next;}linklist;voidLength1(linklist*L){linklist*p=L-next;inti=0;while(p){i++；p=p->next;}L->data=i;〃按照题目要求，将表长写入头结点的数据域小。)(2)#definemaxsize1024typedefintdatatype;typedefstruct{datatypedata;intnext;}node;nodenodepool[maxsizej;voidLength2(intL){inti=()9p=nodepool[L].ne

8、xt;whilc(p){i++；p=nodepool[pj.next;}nodepoolfL].data=i