数据结构-1-顺序表的实现

学习资料：数据结构（C语言版） 清华大学出版社

其中部分函数的解释来源于百度百科……

线性表的顺序表示与实现

线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。这种机内表示称作线性表的顺序存储结构或者顺序映像。 关于线性表顺序存储结构的分析：

优点：只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取。 缺点：当作插入或者删除的操作时，需要移动大量的元素。

一、准备阶段： 1、开始前关于程序的头文件和宏定义等相关准备如下：

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 using namespace std;
 4 #define TRUE 1
 5 #define FALSE 0
 6 #define OK 1
 7 #define ERROR 0
 8 #define OVERFLOW -2
 9 #define LIST_INIT_SIZE 100
10 #define LISTINCREMENT 10

2、辅助定义：

typedef int Status;
typedef int ElemType;

定义不同的数据类型名称是为了增强程序的可读性。

日后编写代码长度较大的程序中，若需要进行类型变换（比如换成double）只要写成:“typedef double ElemType; ”就可以了。

3、用结构体构造一个顺序表，定义了顺序表的地址、长度和当前分配的存储容量。代码如下：

1 typedef struct
2 {
3     ElemType *elem;//存储空间的基址
4     int length;//当前长度
5     int listsize;//当前分配的存储容量（以sizeof（ElemType）为单位）
6 } Sqlist;

二、相关函数

1、线性表的初始化

顺序表的初始化操作是为顺序表分配一个预定义大小的输足空间，并且将线性表的当前长度设为0。当空间不足时，可以再一次进行分配，为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。

调试时出现的问题：

一开始代码按照书上写为“&L”（第一行）

可是出现“expected ‘)’ before'&’ token”字眼的错误（当时选择了C语言的编译环境）

后来改为'L'的写法（函数内涉及L的访问用'(L).'/'(L->)'的写法）可以正常运行（这时我改了C++的编译环境）。

原来这是编译环境的问题。第一种‘&L’的写法在C++的编译环境下是也可以正常编译的。而C的编译环境不支持。

1 Status InitList_Sq(SqList *L)
2 {
3     (*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
4     if(!(*L).elem)exit(OVERFLOW);
5     (*L).length=0;
6     (*L).listsize=LIST_INIT_SIZE;
7     return OK;
8 }

在这里用到了malloc函数（动态内存分配）:

头文件：#include

功能：malloc 向系统申请分配指定size个字节的内存空间。

返回值：如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。函数返回的指针一定要适当对齐，使其可以用于任何数据对象 。

2、数据的插入

向指定位置pos插入数据e（插入前判断是否需要增加存储空间，若不够就增加分配）。先移动指针再插入e。需要考虑输入的pos是否合法。

1 Status ListInsert_Sq(SqList *L,int pos,ElemType e)
 2 {
 3     ElemType *newbase,*p,*q;
 4     if(pos<1||pos>(*L).length+1)
 5     {
 6         cout<<"this position is illegal!"<<endl;
 7         return ERROR;
 8     }
 9     if((*L).length>=(*L).listsize)//当前存储空间已满，增加分配
10     {
11         newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
12         if(!newbase) exit(OVERFLOW);//存储分配失败返回“溢出啦！”
13         (*L).elem=newbase;//新基址的赋予
14         (*L).listsize+=LISTINCREMENT;//增加存储容量
15     }
16     q=&((*L).elem[pos-1]);//q就是插入位置
17     for(p=&((*L).elem[L->length-1]); p>=q; --p)
18         *(p+1)=*p;
19     *q=e;
20     (*L).length++;
21     return OK;
22 }

这里用到了realloc（动态内存调整）函数：

头文件：
#include 有些编译器需要#include ，在TC2.0中可以使用alloc.h头文件（TC2.0是什么= =)功能：先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域（注意：原来指针是自动释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。注意：当内存不再使用时，应使用free()函数将内存块释放。3、数据的删除删除指定位置pos的元素，返回该位置元素的值。由于是删除操作，所以先删除，后移动。

1 Status ListDelete_Sq(SqList *L,int pos,ElemType &e)
 2 {
 3     ElemType *p,*q;
 4     if((pos<1)||(pos>(*L).length)) return ERROR;//输入地址不合法
 5     p=&((*L).elem[pos-1]);//p是被删除元素的位置
 6     e=*p;//被删除的值赋给e
 7     q=(*L).elem+(*L).length-1;//表尾元素的定位
 8     for(++p; p<=q; ++p) *(p-1)=*p;
 9     (*L).length--;
10     return OK;
11 }

4、元素的排序

在这里我使用了选择排序法。功能是将顺序表L中的元素按从大到小的位置进行排序。反过来的话改一下大小符号就可以啦！:p

1 void ListSort_Sq(SqList *L)
 2 {
 3     int i, j, tmp, maxn;
 4     for(i=0; i<(*L).length-1; i++)
 5     {
 6         maxn = i;
 7         for(j=i; j<(*L).length; j++)
 8         {
 9             if((*L).elem[maxn]<(*L).elem[j])
10                 maxn=j;
11         }
12         tmp =(*L).elem[i];
13         (*L).elem[i]=(*L).elem[maxn];
14         (*L).elem[maxn]=tmp;
15     }
16 }       /*选择排序法*/

5、查找指定元素的首次出现的位置

功能就是这个函数的字面意思= =…… 恩，在写这个函数之前还要再写个小帮手bool类型compare函数去进行两个元素间的比较，若相同则返回true，否则返回false。

1 bool Compare_Sq(ElemType *a,ElemType *b)
2 {
3     if(*a==*b) return TRUE;
4     else return FALSE;
5 }

接下来就是locate函数啦！返回指定元素首次出现的位置。注意：返回的值是实际位置的-1.

1 Status LocateElem_Sq(SqList *L,ElemType e)
 2 {
 3     int pos;
 4     ElemType *q;
 5     q=(*L).elem;//获取数组的首元素地址
 6     while(pos<=(*L).length&&!Compare_Sq(q,&e))
 7     {
 8         pos++;
 9         q++;
10     }
11     if(pos<=(*L).length)
12         return pos;
13     else return 0;
14 }

在调试的时候出现了这种错误：

C:UsersWinwinsheepDesktopxianxingbiao.cpp||In function 'Status LocateElem_Sq(SqList, ElemType)':|

C:UsersWinwinsheepDesktopxianxingbiao.cpp|97|error: invalid conversion from 'ElemType {aka int}' to 'ElemType {aka int}' [-fpermissive]|

C:UsersWinwinsheepDesktopxianxingbiao.cpp|86|error: initializing argument 2 of 'bool Compare_Sq(ElemType, ElemType*)' [-fpermissive]|

上网查找了很多都没弄明白这究竟是什么问题。后来改了locate函数的第六行（原来是(q,e)，我在e的前面加了个地址符。

我猜大概是因为compare这个小函数里是用指针进行运算的，而在locate函数中q本来就定义为指针类型，而e是ElemType类型。所以需要在e传入时加一个取址符保证它的一致性。

6、两个顺序表的归并

将两个顺序表L1和L2归并到L3中。函数中会为L3分配可以容下L1和L2的内存，归并后按照小顺序表自身原来的顺序排序。

1 void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc)
 2 {
 3     //已知顺序线性表La与Lb的元素按值非递减排列
 4     //归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
 5     ElemType *pa,*pb,*pa_last,*pb_last,*pc;
 6     pa=(*La).elem;
 7     pb=(*Lb).elem;
 8     (*Lc).listsize=(*Lc).length=(*La).length+(*Lb).length;
 9     pc=(*Lc).elem=(ElemType *)malloc((*Lc).listsize*sizeof(ElemType));
10     if(!(*Lc).elem) exit(OVERFLOW);//存储分配失败
11     pa_last=(*La).elem+(*La).length-1;
12     pb_last=(*Lb).elem+(*Lb).length-1;//？？？
13     while(pa<=pa_last&&pb<=pb_last)//归并
14     {
15         if(*pa<=*pb) *pc++=*pa++;
16         else *pc++=*pb++;
17     }
18     while(pa<=pa_last) *pc++=*pa++;//插入La的剩余元素
19     while(pb<=pb_last) *pc++=*pb++;//插入Lb的剩余元素
20 }

我也没弄明白11 12行代码的意思，明天弄明白了上来更改……

7、顺序表的输出

恩，就是按顺序输出顺序表里的元素。

1 void Output_L(SqList *L)
2 {
3     int i;
4     for(i=0; i<(*L).length; i++)
5         printf("%d ",(*L).elem[i]);
6     cout<<endl;
7     cout<<"The length of the SqList:"<<(*L).length<<endl<<endl;
8 }

8、顺序表的销毁

销毁指定的顺序表。（用完就删，做一个节俭的好孩子，日常生活已经那么穷了，唉，内存更不能浪费啊！万一电脑崩溃了……QAQ）

1 void Output_L(SqList *L)
2 {
3     int i;
4     for(i=0; i<(*L).length; i++)
5         printf("%d ",(*L).elem[i]);
6     cout<<endl;
7     cout<<"The length of the SqList:"<<(*L).length<<endl<<endl;
8 }

三、主函数

在顺序表的实现过程中，不要想着一下子就写完，写完了就能立刻嗖嗖地运行起来。边走边调试会简单得多。

在主函数中记录了我每一个函数的调用和调试。

如果有写的不好的地方希望指出来，一定改正。

1 int main()
 2 {
 3     SqList* L1=new SqList();
 4     InitList_Sq(L1);//初始化函数的测试
 5     (*L1).length=10;
 6 
 7     for(int i=0; i<(*L1).length; i++)
 8     {
 9         (*L1).elem[i]=i;
10     }
11     Output_L(L1);
12 
13     int a,n;
14     cout<<"Insert test"<<endl<<"Please input a legal position :"<<endl;
15     cin>>a;
16     cout<<"Please input the data:"<<endl;
17     cin>>n;
18     ListInsert_Sq(L1,a,n);
19     Output_L(L1);
20     cout<<"Delete test"<<endl<<"Please input a legal position :"<<endl;
21     cin>>a;
22     ListDelete_Sq(L1,a,n);
23     cout<<"The delete data is "<<n<<endl;
24     Output_L(L1);
25 
26     cout<<"Sort test"<<endl;
27     ListSort_Sq(L1);
28     Output_L(L1);
29 
30     cout<<"Now you can create a personal SqList.Please input ten data."<<endl;
31     SqList* L2=new SqList();
32     InitList_Sq(L2);
33     for(int i=0; i<10; i++)
34     {
35         int c;
36         cin>>c;
37         ListInsert_Sq(L2,i+1,c);
38     }
39 
40     Output_L(L2);
41     ListSort_Sq(L2);
42     Output_L(L2);
43 
44 
45     cout<<"Lotate test"<<endl<<"Please input a data:"<<endl;
46     cin>>a;
47     int b=LocateElem_Sq(L2,a);
48     if(b) cout<<"The first position of "<<a<<" is "<<b+1<<endl;
49     else cout<<"Fail to find '"<<a<<"' in List2."<<endl;
50 
51 
52     cout<<"MergeList test"<<endl;
53     SqList* L3=new SqList();
54     MergeList_Sq(L1,L2,L3);
55     Output_L(L3);
56 
57     DestroyList_Sq(L1);
58     DestroyList_Sq(L2);
59     DestroyList_Sq(L3);
60     return 0;
61 }

附一张运行的图

四、个人收获与思考

^_^

顺序表是这门课最为基本和应该来说算是最简单的数据结构。

上机之前内心有些焦虑，可能作为一个新手有对长长的代码量具有些许害怕。不过真的一步一步去写，当整个程序完成的时候特别有成就感啊！

加油。

本文中若有不正确的地方望指出与海涵，定更正。

原文链接: https://www.cnblogs.com/AKsnoopy/p/4876123.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍