第2章 线性表 线性结构 是一个数据元素的有序集合。.

Presentation on theme: "第2章 线性表 线性结构 是一个数据元素的有序集合。."— Presentation transcript:

1 第2章 线性表 线性结构 是一个数据元素的有序集合。

2 第2章 线性表 线性结构特征： 1、有且仅有一个开始结点。 2、有且仅有一个终端结点。
3、除开始结点和终端结点外的结点都最多只有一个直接前驱和一个直接后继。

3 第2章 线性表 2．1 线性表的基本概念 2．2 线性表的顺序存储结构及其运算 2．3 线性表的链式存储结构及其运算
2．4 顺序表和链表的比较 2．5 线性表的应用

4 2．1 线性表的基本概念 2．1．1 线性表的定义 由数据类型相同的n(n≥0)个数据元素组成的有限序列。
记为（a1,a2, …,ai-1,ai,ai+1, …,an） 其中，n为表长，n=0时称为空表；下标i表示数据元素的位序。通常，用L表示一个线性表。

5 2．1．2 线性表及其基本操作 1．初始化线性表InitList(L) 初始条件 线性表L不存在。 运算结果 构造一个空的线性表。
运算结果 构造一个空的线性表。 （n=0）。

6 2．1．2 线性表及其基本操作 2．求线性表的长度LenList(L) 初始条件 表L存在。 运算结果 返回线性表中所含数据元素的个数。

7 3．读取线性表中的第i个数据元素GetfromList(L，i)
运算结果 返回线性表L中第i个元素的值或地址。如果线性表为空，或者i超过了线性表的长度，则报错。

8 4．按值查找SearchList(L，x)

9 5．插入操作InsertList(L，i，x)
初始条件 线性表L存在，i表示新元素将要插入的位置，插入位置正确(1≤i≤n+1，n为插入前的表长)。 运算结果 在L的第i个位置上插入一个值为x的新元素，该元素成为新的第i个数据元素。

10 6．删除操作：DeleteList(L，i)
运算结果 如果L为空表或位序i大于线性表长度，则报错。在L中删除位序为i的数据元素。

11 7．PriorElement(L，i) 8 ．NextElement(L，i) 9. clearList(L) 10. ListEmpty(L) 根据以上基本操作，可以实现一些复杂的操作。

12 例如： 假设利用线性表LA和LB分别表示两个集合A和B，现要求构成一个新的集合A=AUB。要求对线性表作如下操作：扩大线性表LA，将存在于LB中而不存在线性表LA中的数据元素插入到线性表LA中去。

13 1、LB中依次取出每个元素。 2、依次在LA中进行查找。 3、若不存在，则插入之。

14 线性表的顺序存储结构是指用一组地址连续(存储空间紧邻)的存储单元依次存储线性表的数据元素，用这种存储形式存储的线性表称为顺序表。
2．2 线性表的顺序存储结构及其运算 2．2．1 顺序表 线性表的顺序存储结构是指用一组地址连续(存储空间紧邻)的存储单元依次存储线性表的数据元素，用这种存储形式存储的线性表称为顺序表。

15 首地址 起始地址 基地址 存储地址 内存状态 元素a1 b 元素a2 b+m …….. 元素ai b+(i-1)*m ……..
每个元素所占用 的存储单元个数 元素an b+(maxlen-1)*m Loc(元素i)=b +（i-1)*m 图2.1 线性表的顺序存储示意图

16 Loc(ai+1)=Loc(ai)+c l≤i≤n Loc(ai)=Loc(a1)+(i-1)c
设每个元素占用c个存储单元，则第i+1个数据元素的地址为： Loc(ai+1)=Loc(ai)+c l≤i≤n Loc(ai)=Loc(a1)+(i-1)c

17 #define MAXSIZE 100 typedef struct {DataType elem[MAXSIZE]; /*存放顺序表的容量*/ int length; /*顺序表的实际长度*/ } Sqlist;

18 typedef struct { DataType *elem; /*线性表的基地址*/ int length; /*线性表当前的长度*/ int listsize; /*线性表当前分配的存储容量*/ }SeqList;

19 2．2．2 顺序表基本运算的实现 1．初始化 Status InitSeqList(SeqList *L)
{ /*操作结果：构造一个空的顺序线性表*/ L>elem=(DataType*)malloc(LIST_INIT_SIZE*sizeof(DataType)) if(!L->elem) exit(OVERFLOW); /* 存储分配失败*/ L->length=0; /* 空表长度为0*/ L->listsize=LIST_INIT_SIZE; /*初始存储容量*/ return OK;}

20 2．插入运算 在表的序号为i的元素前面插入e。 原表 (a1,a2,…,ai-1,ai,ai+1,…,an)
新表(a1,a2,…,ai-1,e,ai, ai+1,…,an) i的合法取值范围1≤i≤n+1

21 Status InsertSeqList(SeqList *L,int i,DataType e)
{ /*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1*/ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/ DataType *q,*p; if(i<1||i>L->length+1) /* i值不合法*/ return ERROR; else if(L->length>=L->listsize) /*当前存储空间已满,增加分配*/ { printf("顺序表已满");return ERROR;} else { q=L->elem+i; /* q为插入位置*/ for(p=L->elem+L->length;p>=q;--p) /* 插入位置及之后的元素右移*/ *(p+1)=*p; *q=e; /*插入e*/ ++L->length; /*表长增1*/ return OK;} }

22 时间复杂度为O(n） 在i位置插入e，从ai到an都要向下移动一个位置，共需要移动n-i+1个元素，而i的取值范围为1≤i≤n+1。
插入在i位置的概率为Pi=1/(n+1)。 时间复杂度为O(n）

23 3．删除运算 删除表中第i个元素。 原表 (a1, a2, …, ai-1, ai, ai+1, …, an) 新表 (a1, a2, …, ai-1, ai+1, …, an) i的取值范围1≤i≤n

24 int DeleteSeqList(SeqList *L,int i)
{ /* 初始条件：线性表L已存在，1≤i≤ListLength(L)*/ int j; if(i<1||i>L->length) /* i值不合法*/ { printf("不存在第i个元素!\n"); return 0; } else { for(j=i;j<L->length;j++) L->elem[j]=L->elem[j+1]; /* 向上顺序移动元素*/ L->length--; /* 表长减1*/ return 1;} }

25 删除第i个元素，元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，Pi=1／n，则有
时间复杂度为O(n）

26 4．按值查找 在线性表中查找与给定值x相等的数据元素。

27 while(j<=L->length&&L->elem[j]!=x) j++; if(j>L->length)
Status SearchSeqList(SeqList *L, DataType x) { int j=l; while(j<=L->length&&L->elem[j]!=x) j++; if(j>L->length) return(-1); else return j; ／*返回x所在位置的位序*／ } 时间复杂度为O(n）

28 顺序表优点： （1）顺序表随机存取表中元素。 （2）顺序表使用的方法简单，容易编程。 （3）无须增加额外的指针域空间。 缺点： （1）插入、删除操作的效率非常低。 （2）需要预先分配足够大的存储空间，其存储空间长度通常要被预设为线性表使用过程中表长的最大值。

29 2.3 线性表的链式存储结构及其运算 通过指针反映元素之间的关系，不要求逻辑上相邻的元素在物理位置上也相邻，所以该方法可以克服顺序表的上述缺点，但随之而来的却是随机存取性能的消失。

30 2．3．1 单链表存储结构 链表中结点的结构如下： data next 数据域，存放数据信息 指针域，指向下一个数据单元

31 单链表的结点结构如下。 typedef struct node { ／*单链表结点结构*／ DataType data ;/* DataType 可以是任何相应的数据类型如int,char等*/ struct node *next; } LinkList;

32 a1 a2 … ... an ^ 头指针和头结点 头指针 头指针 空指针  头结点 线性表为空表时， 头结点的指针域为空

33 1、建立单链表。 头插入法，每输入一个不为零整数就建立结点，把结点插入到当前链表的表头之前； 尾插入法，把新生成的结点插入到当前链表的表尾结点之后。 考虑：区别是什么？

34 （1）头插入法建表 LinkList *AddHead1() { /*用头插入法建立带头结点的单链表*/ int x;
LinkList *head,*p; head=( LinkList*)malloc(sizeof(LinkList)); head->next=NULL; /*初始化一个空链表，L为头指针*/ scanf(“%d”,&x); /*x是和链表结点的数据域值具有相同类型的变量*/ while(x!=flag) /*flag为结束输入的标志*/ { p=(LinkList *)malloc(sizeof(LinkList));/*生成新的结点*/ p->data=x; /*输入元素值*/ p->next= head ->next; head ->next=p; /*插入到表头*/ scanf(“%d”,&x); /*读入下一个元素的值*/ } return head;

35 （2）尾插入法建表 LinkList *AddHead( ) {/*尾插入法建立一个不带头结点的单链表，返回表头指针*/
LinkList *head=NULL,*q=head,*p; int x ; scanf(“%d”,&x); while(x!=flag) { p=(LinkList*)malloc(sizeof(LinkList)); p->data=x; if(head==NULL) head=p; /*第一个结点的处理*/ else q->next=p; /*其他结点的处理*/ q=p; /*q指向新的尾结点*/ } if(q!=NULL) q->next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return head;

36 2、初始化单链表 void InitList(LinkList *head) {/*初始化带头结点的链表头指针*/
head=(LinkList*)malloc(sizeof(LinkList)); head->next=NULL; }

37 3、单链表中插入元素 在P所指向的结点之后插入新的结点x
① s=( LinkList *)malloc(sizeof (LinkList)); /*申请新结点，用s保存地址*/ ② s->data=x; /*把值x写入s所指的结点的数据域*/ ③ s->next=p->next; /*令s->next指向p所指结点的下一个结点（或NULL）*/ ④ p->next=s; /*令p->next指向s所指结点*/ 时间复杂度为O(1)。 P a b P a b x S

38 4、单链表中删除元素 p q ai-1 ai-1 ai ai+1
q = p->next; p->next = q->next; e = q->data; free(q); p q ai-1 ai-1 ai ai+1

39 5、单链表按序号查找 LinkList *GetNode(LinkList *head,int i)
{/*在带头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULL*/ LinkList *p=head; int j=0; while(p->next&&j<i) { j++; p=p->next; /*p右移一个结点*/ } if(j==i) return p; else return NULL;

40 6、单链表按值查找 {/*在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL*/
LinkList *LocateNode(LinkList *head，int x) {/*在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL*/ LinkList *p=head->next; while(p&&p->data!=x) p=p->next; return p; }

41 7、求单链表长度 int ListLen(LinkList *head) {/*在带头结点的单链表求表的长度*/ int len=0;
LinkList *p=head ; while(p->next!=NULL) { len++; p=p->next; } return len; 算法时间复杂度为O(n)。

42 2．3．2 循环单链表存储结构 a a … an 和单链表的差别在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 如果将链表头指针放在头结点的指针域就构成空循环单链表

43 利用尾指针完成链表L和pL相连的操作。 ① p=L–>next; /*保存L的头结点指针*/ ② L->next=pL->next->next; /*头尾连接*/ ③ free(pL->next); /*释放pL所指链表的头结点*/ ④ pL->next=p; /*重新构成循环单链表*/

44 2．3．3双向链表存储结构 结点中包含有双向指针的链表。 head head

45 typedef struct node { ListDT data; struct node *prior,*next; }DNode,*DLink;

46 双向链表的插入操作 ① q=(DNode*)malloc(sizeof(DNode)); ② q->data=d;
③ q->next=ptr->next; ④ if(ptr->next)ptr->next->prior=q; ⑤ q->prior=ptr; ⑥ ptr->next=q;

47 ① q=(DNode*)malloc(sizeof(DNode));
② q->data=d; ③ q->prior=ptr->prior; ④ ptr->prior->next=q; ⑤ q->next=ptr; ⑥ ptr->prior=q;

48 双向链表的删除操作 ai-1 ai-1 ai ai+1 p p->next = p->next->next;
p->next->prior = p;

49 2.4 顺序表和链表的比较

50 1、顺序表 #define MAXSIZE 100 typedef struct {DataType elem[MAXSIZE];
/*存放顺序表的容量*/ int length; /*顺序表的实际长度*/ } Sqlist;

51 插入运算:在表的序号为i的元素前面插入e。
元素an …….. 元素ai 元素a2 元素a1 for(j=n;j>=i;j--) a[j+1]=a[j];

52 删除运算:删除表中第i个元素。 for(j=i;j<n;j++) a[j]=a[j+1]; 元素a1 元素a2 元素ai 元素an
…….. 元素ai 元素a2 元素a1 for(j=i;j<n;j++) a[j]=a[j+1];

53 顺序表优点： （1）可以按序号随机访问表中元素。 （2）比较简单，容易编程。 （3）无须为表示表中元素之间的逻辑关系而增加额外的指针域空间。 缺点： （1）做插入或删除元素的操作时，可能会发生大量的数据移动。 （2）需要预先分配足够大的存储空间。

54 2．链表 单链表存储结构 data next 数据域，存放数据信息 指针域，指向下一个数据单元

55 单链表的结点结构如下： typedef struct node { ／*单链表结点结构*／ DataType data ;/* DataType 可以是任何相应的数据类型如int,char等*/ struct node *next; } LinkList;

56 插入运算 s->next=p->next; p->next=s; 时间复杂度为O(1) P a b P a b x S

57 删除运算 q p ai-1 ai-1 ai ai+1 q = p->next; p->next = q->next;
e = q->data; free(q); q p ai-1 ai-1 ai ai+1

58 链表优点： （1）做插入或删除结点的操作，不会发生数据移动，操作效率比较高。 （2）存储空间占用量是动态的，无须事先分配备用空间。 缺点： （1）不具备随机访问表中元素的特性。 （2）要频繁使用指针，编程难度较大。 （3）需要为表示表中元素之间的逻辑关系而增加额外的指针域空间。

59 Pn(x)=P0+P1x+P2x2+…+Pnxn
2．5 线性表的应用 【例1】一元多项式写成 Pn(x)=P0+P1x+P2x2+…+Pnxn 线性表表示 P=(P0，P1，P2，…，Pn) 例如： A(x)=1+2x100 +3x1000+4x10000 A=((1，0)，(2，100)，(3，1000)，(4，10000))

60 单链表表示：

61 typedef struct pnode {/*多项式结点结构*/ float coef;/*表示多项式的系数*/ int exp; /*表示多项式的指数*/ stuct pnode *next; }Poly;

62 分三种情况： (1)p->exp<q->exp，*p应为多项式的一项； (2)p->exp==q->exp，则将两个结点中的系数相加，若相加为零，则释放指针p和q所指结点，否则修改*p结点的coef系数域，并释放指针q所指结点； (3)p->exp>q->exp，*q应为多项式的一项，把*q插入到*p之前。

63

64 其算法如下： Poly PolyAdd(Poly *pa，Poly *pb) {/*求两多项式之和，多项式用带头结点的单链表表示，pa，pb为头指针*/ Poly *p,*q,*r,*s; int x; p=pa->next; r=pa; /*r为p的前驱指针*/ q=pb->next; free(pb); while(p!=NULL&&q!=NULL) if(p->exp<q->exp) {/*指针顺链向后移动*/ r=p;p=p->next;} else if(p->exp==q->exp) { x=p->coef+q->coef; if(x==0) {r->next=p->next; free(p);/*释放P所指结点*/ } else{ p->coef=x; r=p; } p=r->next; s=q->next;/*s为辅助指针，指向q的后继结点*/ free(q); /*释放q所指结点*/ q=s; } else{/*q所指结点插入到r,p所指结点之间*/ s=q->next;r->next=q; q->next=p; r=q; q=s; } if(q!=NULL) r->next=q;/*将pb表的剩余结点插人到pa表尾*/ return(pa); /*返回新多项式表头指针，与pa一致*/

65 【例2】为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号。
（1）存储结构类型定义 /*员工通讯信息的结构类型定义*/ typedef struct { char num[5]; /*员工编号*/ char name[8]; /*员工姓名*/ char phone[9]; /*办公室电话号码*/ char call[12]; /*手机号码*/ }DataType;

66 /*通讯录单链表的结点类型*/ typedef struct node { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode,*LinkList;

67 ①建立通讯录链表 LinkList CreatList(void) /*建立一个通讯录链表*/ { LinkList head,s,p,q; char ch; head=(ListNode *)malloc(sizeof(ListNode)); /*创建头结点*/ head->next=NULL; p=head; do{ s=(ListNode *)malloc(sizeof(ListNode)); printf("请输入姓名:"); scanf("%s",s->data.name); printf("请输入编号:"); scanf("%s",s->data.num); printf("请输入电话号码:"); scanf("%s",s->data.phone); printf("请输入手机号码:"); scanf("%s",s->data.call); s->next=p->next; p->next=s; printf("继续输入下一记录吗(y/n)?"); scanf("\n%c",&ch); } while(ch=='y'|| ch=='Y'); return head; /*返回头结点指针*/}

68 ②查询功能：可以按照编号或姓名在链表中顺序查找出对应的记录。
ListNode *SearchList(LinkList head) /*查询函数*/ { ListNode *p; int x; /*按照编号或姓名在链表中查找由x的值决定*/ char num[5]; /*员工编号*/ char name[8]; /*员工姓名*/ printf("1. 按编号查询 2.按姓名查询\n"); printf("请选择:"); scanf("%d",&x); if(x==1) { printf("请输入待查人的编号:"); scanf("%s",num); for(p=head;p!=NULL&&strcmp(p>data.num,num)!=0;p=p->next); } else if(x==2) { printf("请输入待查人的姓名:"); scanf("%s",name); for(p=head;p!=NULL&&strcmp(p->data.name,name)!=0;p=p->next); } return p;}

69 ③插入新的记录：将新记录结点插入到头结点之后，成为链表中的第一个记录结点。也可将新记录插入在记录链表的尾部，成为最后一条记录。
void InsertList(LinkList head,ListNode *p) { p->next=head->next; head->next=p; }

70 ④删除记录：可以按照编号或姓名在链表中顺序查找出对应的记录，然后将其删除。本函数调用查询函数。
void DelNode(LinkList head) { LinkList p,q; char ch; p=SearchList(head); if(!p) { printf("没有找到此人的记录\n"); return;} printf("确定要删除吗?(y/n)"); scanf("\n%c",&ch); if(ch=='n') return; for(q=head;q!=NULL&&q->next!=p;q=q->next); q->next=p->next; free(p); printf("删除成功\n");}

71 ⑤查看全部记录：从第一个结点到最后一个结点依次输出所有记录。
void PrintList(LinkList head) { LinkList p; p=head->next; printf(“编号 姓名 电话号码 手机号码\n”); while(p!=NULL) { printf(" %s%s %s %s\n", p->data.num,p->data.name,p->data.phone,p->data.call); p=p->next; }

72 结 束！