通信原理大综合课件软件

1Character

00000线性表2

2．2线性表2.2.1线性表的基本概念线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，...，ai，...，an线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素)3在线性表上常用的运算有：初始化求长度取元素修改前插删除检索排序4设线性表的基地址为：LOC(a1),ai的存储地址为：

LOC(ai)=LOC(a1)＋(i-1)*k1<=i<=na1a2aian……Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*k

2.2.2线性表的存储结构及其运算线性表的顺序存储结构

把数据元素按照逻辑顺序依次存放到一组连续的存储单元中。5元素1元素2……..元素n……..01n-1V[0]

线性表的顺序存储结构——可用C语言中的一维数组来描述.#defineM100//定义M为常数100，M的值作为数组的最大容量

intV[M]；//V是数组的名字，假设数组中的数据元素是整型类型intlength；//当前长度V[1]V[n]V[M-1]6…..a2a1alength…..ai+1ai01i-1ilength-11顺序表的插入运算ai-1…..a2a1alength

…ai+1ai

xP（P+1）q

ai-1…..

a2

a1

ai

ai+1

…alength

alength

…

…ai+1

ai

x7intinsq(inti,intx,intV[],intM,int*p）{/*在线性表中V中第i个元素之前插入x，M是存储空间大小，p是指针变量，指向存储表长的变量*/intn,j;n=*p;/*获取表长*/if(n==M){printf(“overflow\n”);return(0);}if（i<1‖i>n+1）

{printf(“Itiserror\n”);return(0);}//i值不合法else{for(j=n;j>=i;j--)V[j]=V[j-1];V[j]=X;*p=++n;//表长加1,有p返回到函数调用处

return(1);}}

voidmain(){ intM=10,n=4; intresult,k; staticintV[10]={3,5,7,10};

result=insq(2,4,V,M,&n); if(result==1){printf("success\n"); for(k=0;k<n;k++)printf("%d",V[k]);} elseprintf("failure");}8intdelsq（inti,intV[],int*p){/*在线性表中V中删除第i个元素*/intn,j;if（i<1‖i>n）

{printf(“Thiselementisnotinthelist\n”);return(0);}//i值不合法else

{for(j=i;j<n;j++)V[j-1]=V[j];*p=--n;//表长减1return(1);}}voidmain(){ intM=10,n=4; intresult,k; staticintV[10]={3,5,7,10};

result=delsq(2,V,&n); if(result==1){printf("success\n"); for(k=0;k<n;k++)printf("%d",V[k]);} elseprintf("failure");}顺序表的删除运算9特点：便于随机存取表中的任一个数据元素，做插入、删除时需移动大量元素。静态分配空间，无法动态分配。表中元素个数是动态变化时，按最大空间分配。适用于需要频繁查找操作的线性表10线性表的链式存储结构

是一种常见的重要的数据结构。它是动态地进行存链表储分配的一种结构。线性表的链式存储结构的含义是指逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。每个数据元素对应内存一个存储空间，叫存储结点，简称结点。1112将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。特点：插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。datanextdata域--存放结点值的数据域next域--存放结点的直接后继的地址（位置）的指针域（链域）13a1a2an∧a3L…..typedef

structLNode{intdata;structLNode*next;}listnode;线性表的链式存储结构——可用C语言中的“结构指针”来描述带头结点的线性链表datanext1415①生成结点变量的标准函数

p=(ListNode*)malloc(sizeof(ListNode))；//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中②释放结点变量空间的标准函数free(p)；//释放p所指的结点变量空间③结点分量的访问

利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next④指针变量p和结点变量*p的关系指针变量p的值——结点地址结点变量*p的值——结点内容

(*p).data的值——p指针所指结点的data域的值

(*p).next的值——*p后继结点的地址

1617voidinsertlist(listnode*L,charx){listnode*p,*s;p=L;if(p==NULL)printf("positionerror");s=(listnode*)malloc(sizeof(listnode));s->data=x;s->next=p->next;p->next=s;}babaxPP5单链表的插入运算S18ai-1a1aiai+1headprvoiddeletelist(listnode*p){listnode*r;if(p->next!=NULL){r=p->next;p->next=r->next;free(r);}}单链表的删除运算19线性链表的查找操作listnode*reseach(listnode*h,intx){listnode*p;p=h;while(p!=NULL&&p->data!=x)p=p->next;return(p);}20.循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。.双向链表