数据结构-线性表
1.线性表：n个数据元素的有序集合。
线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。 线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。
特征：
1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后一个元素之外，均有唯一的后继(后件)；4．除第一个元素之外，均有唯一的前驱(前件)。
java中的List接口，就是线性表。ArrayList就是顺序线性表，LinkdList就是链表线性表。
2.线性表的顺序表示：ArrayList
一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。
优点：在于随机访问元素，
缺点：插入和和删除的时候，需要移动大量的元素。
c语言实现代码：
1.//Tst.cpp:Dfinsthntrypointforthconsolapplication.
2.//
3.
4.#includ"stdafx.h"
5.#includstdio.h
6.#includ"stdlib.h"
7.//宏定义
8.#dfinTRUE1
9.#dfinFALSE0
10.#dfinOK1
11.#dfinERROR0
12.#dfinINFEASIBLE-1
13.#dfinOVERFLOW-2
14.
15.#dfinLT(a,b)((a)(b))
16.#dfinN=
17.
18.#dfinLIST_INIT_SIZE//线性表初始空间分配量
19.#dfinLISTINCREMENT10//线性表空间分配的增量
20.
21.typdfintStatus;
22.typdfintElmTyp;
23.
24.typdfstructLNod{
25.ElmTyp*lm;//存储空间的基地址
26.intlnght;//当前的长度
27.intlistsiz;//当前分配的存储容量
28.}SqList;
29.
30./**
31.*构造空的线性表
32.*/
33.
34.StatusinitList(SqListL,intlnght){
35.if(lnght==0)lnght=LIST_INIT_SIZE;
36.L.lm=(ElmTyp*)malloc(lnght*sizof(ElmTyp));
37.if(!L.lm)xit(OVERFLOW);//分配存储空间失败
38.L.lnght=0;//初始空表长度为0
39.L.listsiz=lnght;//初始存储容量为
40.rturnOK;
41.}
42./************************************************************************/
43./*在第i位置插入
44.*/
45./************************************************************************/
46.StatusinsrtList(SqListL,ElmTyp,inti){
47.ElmTyp*p,*q;
48.if(i0
iL.lnght)rturnERROR;//i值不合法
49.if(L.lnght=L.listsiz){
50.ElmTyp*nwbas=(ElmTyp*)ralloc(L.lm,(L.listsiz+LISTINCREMENT)*sizof(ElmTyp));
51.if(!nwbas)rturnOVERFLOW;//存储分配失败
52.L.lm=nwbas;//新基值
53.L.listsiz+=LISTINCREMENT;//增加存储容量
54.}
55.q=L.lm[i];//q为插入的位置
56.for(p=L.lm[L.lnght];p=q;--p){
57.*p=*(p-1);//i元素之后的元素往后移动
58.}
59.*q=;//插入
60.L.lnght+=1;
61.rturnOK;
62.
63.}
64./************************************************************************/
65./*快速排序
66.*/
67./************************************************************************/
68.voidsortList(SqListL){
69.
70.
71.}
72./************************************************************************/
73./*删除第i位置元素，并用返回其值*/
74./************************************************************************/
75.StatusdltListElm(SqListL,inti,ElmTyp){
76.int*p,*q;
77.if(i0
iL.lnght)rturnERROR;//i值不合法
78.q=L.lm[i];//被删除元素的位置为i，L.lm就是数组名,
79.=*q;//被删除元素的值赋值给
80.for(p=q;p(L.lm+L.lnght);p++){//元素左移
81.*p=*(p+1);
82.}
83.--L.lnght;
84.rturnOK;
85.}
86.
87./************************************************************************/
88./*快速排序
89.*/
90./************************************************************************/
91.
92.intpartition(SqListL,ElmTyplow,ElmTyphigh){
93.ElmTyppivotky=L.lm[low];//枢轴记录关键字
94.whil(lowhigh){//从表的两端向中间扫描
95.whil(lowhighL.lm[high]=pivotky)--high;//高端位置扫描
96.L.lm[low]=L.lm[high];//交换数据，小于pivotky移到低端
97.L.lm[high]=pivotky;
98.
99.whil(lowhighL.lm[low]=pivotky)++low;//低端扫描
.L.lm[high]=L.lm[low];//交换数据大于pivotky移到高端
.L.lm[low]=pivotky;
.}
.rturnlow;
.}
.
.voidquickSort(SqListL,ElmTyplow,ElmTyphigh){
.intpivot;
.if(lowhigh){
.pivot=partition(L,low,high);
.quickSort(L,low,pivot-1);//低端子表排序
.quickSort(L,pivot+1,high);//高端子表排序
.}
.
.}
.
.
./************************************************************************/
./*
.合并两个线性表
.*/
./************************************************************************/
.
.voidmrgList(SqListLa,SqListLb,SqListLc){
.ElmTyp*pa,*pb,*pc;
.Lc.listsiz=La.lnght+Lb.lnght;
.initList(Lc,Lc.listsiz);//初始化LC\pc=Lc.lm;
.Lc.lnght=Lc.listsiz;
.pc=Lc.lm;
.pa=La.lm;
.pb=Lb.lm;
.whil(pa=La.lm[La.lnght-1]pb=Lb.lm[Lb.lnght-1]){
.if(*pa=*pb)*pc++=*pa++;
.ls*pc++=*pb++;
.}
.whil(pa=La.lm[La.lnght-1])*pc++=*pa++;//插入La的剩余元素
.whil(pb=Lb.lm[Lb.lnght-1])*pc++=*pb++;//插入Lb的剩余元素
.
.}
.
./************************************************************************/
./*打印list
.*/
./************************************************************************/
.voidprintList(SqListL){
.printf("当前值:");
.for(inti=0;iL.lnght;i++){
.printf("%d",*(L.lm+i));//L.lm为首地址
.}
.printf("\r\n");
.}
.
.voidmain()
.{
.SqListLa,Lb,Lc;
.ElmTyp;
.intinit,i;
.init=initList(La,LIST_INIT_SIZE);
.intdata[6]={5,3,6,2,7,4};
.for(i=0;i6;i++){
.insrtList(La,data[i],i);
.}
.printf("LA:\r\n");
.printList(La);
.dltListElm(La,3,);
.printList(La);
.insrtList(La,,3);
.printList(La);
.
.//排序
.quickSort(La,0,La.lnght-1);
.printList(La);
.
.printf("LB:\r\n");
.initList(Lb,LIST_INIT_SIZE);
.intBdata[5]={1,3,2,4,6};
.for(i=0;i5;i++){
.insrtList(Lb,Bdata[i],i);
.}
.//排序
.quickSort(Lb,0,Lb.lnght-1);
.printList(Lb);
.
.mrgList(La,Lb,Lc);
.printList(Lc);
.
.}
3.线性表的链表表示LinkdList
一般使用链表来描述。
优点：对于新增和删除操作add和rmov和方便。不需要移动元素。
缺点：不方便随机访问元素，LinkdList要移动指针
代码实现：
1.//Tst.cpp:Dfinsthntrypointforthconsolapplication.
2.//
3.#includ"stdafx.h"
4.#includstdio.h
5.#includ"stdlib.h"
6.//宏定义
7.#dfinTRUE1
8.#dfinFALSE0
9.#dfinOK1
10.#dfinERROR0
11.#dfinINFEASIBLE-1
12.#dfinOVERFLOW-2
13.
14.#dfinLT(a,b)((a)(b))
15.#dfinN=
16.
17.typdfintStatus;
18.typdfintElmTyp;
19.
20.typdfstructLNod{
21.ElmTypdata;
22.structLNod*nxt;
23.}LNod,*LinkList;
24.
25./************************************************************************/
26./*
27.初始化链表
28.*/
29./************************************************************************/
30.StatusinitList(LinkListL){
31./*单链表的初始化*/
32.L=(LinkList)malloc(sizof(LNod));//申请一个头节点
33.if(!L)xit(OVERFLOW);//申请空间失败
34.L-nxt=NULL;//建立一个带都节点的空链表
35.rturnOK;
36.
37./*
38.需要改变指针的指针，所以参数必须是引用或者是*L:
39.(*L)=(Lnod*)malloc(sizof(Lnod));
40.(*L)-nxt=NULL;
41.rturn1;
42.*/
43.
44.}
45.
46./************************************************************************/
47./*
48.创建链表
49.*/
50./************************************************************************/
51.voidcratList(LinkListL,intn){
52./*单链表的初始化*/
53.if(!L){
54.initList(L);
55.}
56.ElmTypdata;
57.LinkListp,q=L;
58.printf("输入节点数据的个数%d：\r\n",n);
59.for(inti=0;in;i++){
60.p=(LinkList)malloc(sizof(LNod));//申请一个新节点
61.scanf("%d",data);
62.p-data=data;
63.p-nxt=q-nxt;
64.q-nxt=p;
65.q=p;
66.}
67.}
68./************************************************************************/
69./*在第i位置插入
70.*/
71./************************************************************************/
72.StatusinsrtList(LinkListL,ElmTyp,inti){
73.LinkLists,p=L;
74.intj=0;
75.whil(pji){//寻找i节点
76.p=p-nxt;
77.j++;
78.}
79.if(!p
ji)rturnERROR;
80.s=(LinkList)malloc(sizof(LNod));//生成新节点
81.s-data=;s-nxt=p-nxt;//插入L中
82.p-nxt=s;
83.rturnOK;
84.
85.}
86.
87./************************************************************************/
88./*删除第i位置元素，并用返回其值*/
89./************************************************************************/
90.StatusdltListElm(LinkListL,inti,ElmTyp){
91.LinkListp,q;
92.intj=0;
93.p=L;
94.whil(pji){
95.p=p-nxt;
96.++j;
97.}
98.if(!p-nxt
ji)rturnERROR;//删除的位置不对
99.q=p-nxt;p-nxt=q-nxt;
.=q-data;fr(q);//释放节点
.rturnOK;
.}
.
.
./************************************************************************/
./*插入排序
.*/
./************************************************************************/
.
.voidInsrtSort(LinkListL)
.{
.LinkListlist;/*为原链表剩下用于直接插入排序的节点头指针*/
.LinkListnod;/*插入节点*/
.LinkListp;
.LinkListq;
.
.list=L-nxt;/*原链表剩下用于直接插入排序的节点链表*/
.L-nxt=NULL;/*只含有一个节点的链表的有序链表。*/
.whil(list!=NULL){/*遍历剩下无序的链表*/
.nod=list,q=L;
.whil(qnod-dataq-data){
.p=q;
.q=q-nxt;
.}
.
.if(q==L){/*插在第一个节点之前*/
.L=nod;
.}ls{/*p是q的前驱*/
.p-nxt=nod;
.}
.list=list-nxt;
.nod-nxt=q;/*完成插入动作*/
.
.}
.}
.
.
.
./************************************************************************/
./*
.合并两个线性表
.*/
./************************************************************************/
.
.voidmrgList(LinkListLa,LinkListLb,LinkListLc){
.LinkListpa,pb,pc;
.pa=La-nxt;
.pb=Lb-nxt;
.Lc=pc=La;
.whil(papa){
.if(pa-datapb-data){
.pc-nxt=pb;
.pc=pb;
.pb=pb-nxt;
.}ls{
.pc-nxt=pa;
.pc=pa;
.pa=pa-nxt;
.}
.}
.pc-nxt=pa?pa:pb;
.fr(Lb);
.}
.
./************************************************************************/
./*打印list
.*/
./************************************************************************/
.voidprintList(LinkListL){
.printf("当前值:");
.LinkListp;
.p=L-nxt;
.whil(p){
.printf("%d",p-data);
.p=p-nxt;
.}
.printf("\r\n");
.}
.
.voidmain()
.{
.LinkListLa,Lb,Lc;
.ElmTyp;
.intinit,i;
.printf("LA:\r\n");
.initList(La);
.cratList(La,5);
.insrtList(La,7,3);
.printList(La);
.dltListElm(La,3,);
.printList(La);
.InsrtSort(La);
.printList(La);
.
.printf("Lb:\r\n");
.initList(Lb);
.cratList(Lb,4);
.InsrtSort(Lb);
.printList(Lb);
.
.printf("Lc:\r\n");
.initList(Lc);
.mrgList(La,Lb,Lc);
.printList(Lc);
.
.}
赞赏