第二章线性表

1、第二章线性表1什么是顺序存储结构？什么是链式存储结构？线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素，它的特点是，线性表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai) 和LOC(a i+ 1 ) 。即，以元素在计算机内"物理位置相邻"来表示线性表中数据元素之间的逻辑关系。简言之逻辑相邻，物理相邻。相邻元素之间查一个元素所占的物理空间，因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。线性量的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以

2、是连续的，也可以是不连续的) . 因此，为了表示每个数据元素ai与其直接后继数据元素a i+ 1之间的逻辑关系，对数据元素a i 来说，除了存储其本身的信息之外，还需存储-个指示其直接后继的信息即直接接后继的存储位置 . 这两部份信息组成数据元素ai的存储映映像，称为结点(node) . 它包括两个域:其中存储数据元素信息的称为数据域，存储直接后继存储位置的域称为指针域. 指针域中存储的信息称做指针或链.2线性表的顺序存储结构和链式存储结构各有什么特点？顺序存储结构，逻辑相邻的元素，物理上也相邻，每个结点只需存储数据本身，不许存储逻辑关系，节约存储空间，查找元素方便，但插入或删除元素需要大量移

3、动元素，效率低。适合查找多但插入删除少的情况。链式存储结构，逻辑上相邻的元素，物理上不一定相邻，每个结点除了存储元素本身外，还要存储元素之间的逻辑关系，占用存储空间大，但查找元素都要从头开始，查找费时间，但插入或删除元素不需要大量移动元素，只需要知道插入或删除位置结点的前驱指针，进行简单的指针变换即可。适合查找少，插入删除相对多的情况。3设线性表中数据元素的总数基本不变，并很少进行插入或删除工作，若要以最快的速度存取线性表中的数据元素，应选择线性表的何种存储结构？为什么?用顺序存储，原因在1 和2之间；4线性表的主要操作有哪些？1） InitList(&L) 初始化：构造一个

4、空的线性表L。2）. DestroyList(&L) 销毁：销毁一个业已存在的线性表L。3）. ClearList(&L) 清空：将一业已存在的线性表L重置为空表。4）. ListEmpty(L) 判表空：若L为空表，则返回TRUE；否则返回FALSE 。5） ListLength(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。6） GetElem(L,i,&e) 对给定的线性表L，取第i个数据元素。0iLength(L)-1），用e返回L中第i个数据元素的值。7）. LocateElem(L,e,compare() 定位 返回L中第

5、一个与e满足关系compare( )的数据元素的位序, 若这种数据元素不存在, 则返回0 。8）. PriorElem(L,cur_e,&pre_e) 求前驱：若cur_e是L的数据元素, 且不是第一个, 则用pre_e返回它的前驱, 否则操作失败, pre_e无定义。9）. NextElem(L,cur_e,&next_e)求后继 若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败, next_e无定义。10）. ListInsert(&L,i,e) 插入 在L中第i个位置之前插入新的数据元素e,L的长度加1 。1=<i &l

6、t;=Listlength(L)+111）. ListDelete(&L,i,&e) 删除 删除L的第i个数据元素,并用e返回其值,L的长度减1 。1=<i <=Listlength(L)+112）. ListTraverse(L,visit() 遍历 对给定的线性表L，依次输出L的每一个数据元素。遍历时不许重复13）. Copy(L,C) 复制 将给定的线性表L复制到线性表C中。14）. Merge(A,B,C) 合并 将给定的线性表A和B合并为线性表C。 5简述数组与顺序存储结构线性表的区别和联系。顺序存储结构的线性表，它是用一个结构体变量来描述一个线性表，该变

7、量包含三个分量，一个是一维数组来存储线性表中的元素，一个是线性表的元素个数length ，一个是线性表最大长度。对于线性表中的数组，每个元素必须是连续存放，若是对线性表插入或删除，对应位置需要靠右移或左移来重新保持紧密连接关系。而且插入或删除只能在合理位置（插入在1length +1的位置，且不能越界，删除在1length 的位置上，）。而数组要灵活很多，数组里的元素不必连续存放，插入删除也不必重新保持元素紧密相联，可以在任意位置插入删除元素，只要不越界即可。 6顺序表和链表在进行插入操作时，有什么不同？顺序表插入时，先找到插入位置，然后从表尾部到插入位置的所有结点顺次后移一个元素，再把要插入

8、的元素放在预定位置，插入需要大量移动元素，效率低。而链式存储插入时只需找到要插入元素应在位置的前驱元素的指针，然后开辟新结点，将新元素放入新结点，再用两条语句就把新结点插入链表适当位置了，不需大量移动元素，效率高.7画出下列数据结构的图示：顺序表单链表 双链表循环链表 顺序存储 单链表 双向链表 循环链表a0a1an-1b1a0a1an-1 8试给出求顺序表长度的算法。 ilength t listlelength gth(Seqlist *L) returlength (L->lelength ) ; 9若顺序表A中的数据元素按升序排列，要求将x插入到顺序表中的合适位置，以保证表的有序

9、性，试给出其算法。答：设原表 (1)顺序存储Void Insert(sqllist *L , elemtype x) Int i = 0; While( i < L->length && L ->elemi < X) i+; If( I = L-> length) L ->elemi = X; L->length+ ; Else For(j =L->length 1; j = i ;j-) L->elemj+1 = L->elemj; L->elemj = X; L->length+;(2)链式存储Int

10、insert(slnodetype *h ,Elemtype X) slnodetype *p,*s; p=h;q = h->next; while( p->next !=NULL && q->data < X) p=q; q = q->next;/ if ( p ->next =NULL) s = (slnode *)malloc(sizeof(slnode) ; s->data = X;p ->next = s;s ->next = NULL; return true ; else (s=(slnodetype*)mal

11、loc(sizeof(slnodetype)=NULL) return FALSE; s->data=x; s->next=p->next; p->next=s; return TRUE;10.将一个线性表从第i个位置起拆开，变成两个线性表答：void seperate(link L , int i , link A, link B) int j = 1; link p = L ;while( j<= i -1 &&p !=NULL) j+; P = P->next;if(p =NULL) printf("the i is over

12、flow"); exit(); else q = p->next; p->next = NULL; LA = L; LB -> next = q ; 11把一个值为的结点插到表中值为的结点之前的算法 typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Void insert(link L , elem x , elem y)/采用链式存储的方式 Link p = L; /放的q的前驱Link q = L;While( q != NULL

13、&& q->data !=x) /找到的前驱 P = q;q = q ->next; S = (link)malloc(sizeof(slnode); S ->data = y; s->next = q; p ->next = s;12.将线性表（顺序存储），偶数下标的元素都变成0，奇数下标的元素都置为1；typedef struct ElemType *elem; int length; int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;Change_list (SqList &L)

14、 int i = 0; for ( i = 0; i< L->length ; i+) if(i%2= 0) L->elementi = 0; else L->elementi = 1;13，将线性表中偶数下标的元素都删除，只留下奇数下标的元素构成一个新的线性表；假设用链式存储typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Link insert(link L ,) /设线性表的第一个元素下标是1 link L_even ; L_even

15、 =(link)malloc(sizeof(Lnod); / L_even是新奇数链表的头指针r= L_even; /r是新的奇数链表的尾部指针 i=1;Link p = L->next ; /放的q的前驱 /r放新链表的最后一个结点的指针While( p != NULL ) /是q的前驱If(i %2 = = 1) r->next = p; r = p; P = p->next;14试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。11已知 L为单链表指针,数据结点递增有序,编写表中值从大于MIN开始到小于

16、MAX值为止所有结点完全倒置的算法.typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Void converse(link L , elem x, elem y) Link p = L; /放的q的前驱Link q = L;Link temp;While( q != NULL && q->data <= min ) /是q的前驱P = q; q= q->next;If(q = NULL)Printf(“ the min is to

17、o big”); exit();Protect = q; temp ->next =null; /protect是指向min 结点指针，temp->next存放倒置过的最后一个结点While(q->data < max)N = q->next;/为下一个要处理的结点q->next = temp->next;Temp->next = q;q = N;P ->next = temp->next;Protect ->next = q;15 .递增有序线性表，（同表中元素各不同，另构建一个新表，值为，交集且递增有序答(1)顺序存储voi

18、d merge(Elemtype La, Elemtype Lb, snode *Lc) int i,j,k; int La_length, Lb_length; i=j=0;k=0; La_length=Length(La); Lb_length=Length(Lb); /*取表La,Lb的长度*/ Initiate(Lc); /*初始化表Lc*/ While (I < La_length&&j< Lb_length) a=get(La,i);b=get(Lb,j); if(a<b) +i; else if(a >b)+j;Else Insert(LC

19、->elelm , k+, a); i+;j+; /while LC->length = k; (2)链式存储Void (link a ,link b,link c)Link pa = a ->next, pb = b-next , pc = c;While(pa !=NULL && pb !=NULL)If(pa ->data < pb->data)Pa = pa->next;Else if(pa->data > pb->data)Pb = pb->next;Else /若相等，插入到表中c->next

20、= pa;C = pa;Pa = pa->next;Pb = pb->next;16删除线性表a中第i个元素起的k个元素 顺序存储typedef struct ElemType *elem; int length; int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;Delete_k(SqList &L) int j;   if(i<1|k<0|i+k-1>a.length) return error; For ( j = i;j +k <=L->length ; j+)

21、 Elemj = elemj+k ; 17把x插入递增有序表L中 (顺序，链式都要）Status Insert_SqList(SqList &L,int x)/把x插入递增有序表L中  if(L.length+1>L.listsize) return ERROR;  L.length+;  for(i=L.length-1;L.elemi>x&&i>=0;i-)    L.elemi+1=L.elemi;  L.elemi+1=x;  

22、;return OK;/Insert_SqList 18在无头结点链表L的第i个元素之前插入元素bStatus Insert(LinkList &L,int i,int b)/在无头结点链表L的第i个元素之前插入元素b  p=L;q=(LinkList*)malloc(sizeof(LNode);  q.data=b;  if(i=1)      q.next=p;L=q; /插入在链表头部    else    &#

23、160; while(-i>1) p=p->next;    q->next=p->next;p->next=q; /插入在第i个元素的位置  /Insert 19链表的就地逆置;为简化算法,假设表长大于2 算法如下：void converse(slnodetype *head)slnodetype *p,*q; p=head->next; head->next=NULL;/*带头结点*/ while(p!=NULL) q=p->next; p->next=head->next; head-&g

24、t;next=p; p=q;20把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间void merge1(LinkList &A,LinkList &B,LinkList &C)/   p=A->next;q=B->next;C=A;  while(p&&q)      s=p->next;p->next=q; /将B的元素插入    if(s)          

25、;t=q->next;q->next=s; /如A非空,将A的元素插入        p=s;q=t;  /while/merge1 21删除元素递增排列的链表L中值大于mink且小于maxk的所有元素Status Delete_Between(Linklist &L,int mink,int maxk)/   p=L;  while(p->next->data<=mink) p=p->next; /p是最后一个不大于mink的元素  if(p->next)    /如果还有比mink更大的元素      q=p->next;    while(q->data<maxk) q=q->next; /q是第一个不小于maxk的元素    p->next=q