下面的代碼是項目文件：一個頭文件、一個源文件、一個測試文件

1、頭文件List.h：

#include<iostream> using namespace std; #include<malloc.h>/*定義數據的類型，可以通過修改這里的數據類型，來實現不同類型的線性表 下面的數據類型可以更改，const引用是限制被調用的函數，不能修改主程序的數據，但可以查看，達到保護主程序數據安全。 不需要執行修改操作，而只要查看數據的線性表就用const限制 引用 */ typedef int Status; typedef int ElemType;#define LIST_INIT_SIZE 10 //初始化的空間分配容量 #define LIST_ADD 10 //每次增加的分配空間增量 #define ok 1 #define error 0 #define flow 0//定義一個線性表結構，結構內有分配空間的基地址，分配空間的總長度，當前使用空間的大小。 typedef struct{ElemType* elem; //空間基地址 int length; //當前已經使用的空間的長度 int listsize; //當前分配的空間長度 }SqList;//初始化線性表 Status InitList(SqList& L); //打印線性表 Status Print(SqList L);//銷毀線性表 Status DestroyList(SqList& L);//將線性表清空 Status ClearList(SqList& L);//判斷線性表是否為空 Status ListEmpty(const SqList& L);//返回線性表中元素的個數 Status ListLength(const SqList& L);//獲取線性表中的第i個元素的值 Status Get(const SqList& L, int i, ElemType& e); //如果當前元素cur_e不是第一個數據，就pre_e返回它的前一個數據的值，否則返回error Status PriorElem(const SqList& L, ElemType cur_e, ElemType& pre_e);//如果當前元素不會最后一個，就用next_e返回它的后一個數值，否則返回error Status NextElem(const SqList& L, ElemType cur_e, ElemType& next_e);//在第i個位置前插入數據e, 數據長度加一 Status ListInsert(SqList& L, int i, ElemType e);// 刪除i個位置的數據，數據長度減一,并返回數據 Status ListDelete(SqList& L, int i, ElemType& e);//合并線性表LA和LB，將結果放入LA中 Status Union(SqList& LA, const SqList& B); //合并線性表 Status MergeList(const SqList& LA, const SqList& LB, SqList& LC); //查詢數據的位置 int LocateElem(const SqList& L, ElemType e);//插入n個數據 Status Insert(SqList& L, int n);

2、源文件List.cpp:

#include "List.h" //這是功能實現源文件，其他程序可以通過頭文件包含，使用這里的功能 //初始化線性表 Status InitList(SqList& L){L.elem = (ElemType* )(malloc( LIST_INIT_SIZE * sizeof(ElemType)));//如果地址分配錯誤，就返回0 if(!L.elem) exit(error);//將當前長度設置為0，分配長度設置為初始長度 L.length = 0;L.listsize = LIST_INIT_SIZE;return ok;}//銷毀線性表 Status DestroyList(SqList& L){//如果地 if(!L.elem){cout<<"線性表不存在"<<endl;}else{free(L.elem);L.elem = NULL;}return ok; } //打印線性表 Status Print(SqList L){cout<<"線性表的數據如下："<<endl;if(L.length == 0){cout<<"線性表為空表, 請插入數據后再來打印數據\n\n"<<endl;}for(int i=0; i<L.length; i++){cout<<L.elem[i]<<" ";}cout<<endl; } //將線性表清空 Status ClearList(SqList& L){//如果線性表的當前長度不為0，就將數據全部清空，當前長度設置為0 if(L.length != 0){for(int i=0; i<L.length; i++){L.elem[i] = 0;}L.length = 0;}return ok; }//判斷線性表是否為空 Status ListEmpty(const SqList& L){if(L.length != 0){//不為空表 return ok;}else{//為空表 return error;} }//返回線性表中元素的個數 Status ListLength(const SqList& L){return L.length; } //獲取線性表中的第i個元素的值 Status Get(const SqList& L, int i, ElemType& e){if(i > L.length || i < 0){cout<<"輸入有誤，退出"<<endl;return error;}else{e = L.elem[i-1];return ok;} }//如果當前元素cur_e不是第一個數據，就pre_e返回它的前一個數據的值，否則返回error Status PriorElem(const SqList& L, ElemType cur_e, ElemType& pre_e){int flag = LocateElem(L, cur_e);if(flag == -1){cout<<"找不到數據"<<endl; return error;}if(flag == 0){cout<<"數據不存在直接前驅"<<endl; }else{pre_e = L.elem[flag-1];}} //如果 當前元素不會最后一個，就用next_e返回它的后一個數值，否則返回error Status NextElem(const SqList& L, ElemType cur_e, ElemType& next_e){int flag = LocateElem(L, cur_e);if(flag = -1){cout<<"數據不存在"<<endl; }else if(flag == L.length){cout<<"該數據不存在直接后繼"<<endl;}else{next_e = L.elem[flag+1];} } //在第i個位置前插入數據e, 數據長度加一 Status ListInsert(SqList& L, int i, ElemType e){if(i<1 || i > L.length+1) {cout<<"輸入的位置有問題"<<endl; return error;}if(L.length == L.listsize){//增加LIST_ADD長度的地址空間 L.elem = (ElemType*)(realloc(L.elem, (LIST_ADD) * sizeof(ElemType)));if(!L.elem) exit(flow); //更新分配的長度 L.listsize = L.listsize + LIST_ADD;//取要插入位置的地址 ElemType* q = &(L.elem[i-1]);//如果地址p比插入的地址q大或則等于，就將數據復制到后面一位空間里面，空出地址q的存儲空間 for(ElemType* p = &(L.elem[L.length-1]); p>= q; p--){*(p+1) = *p;} //給地址空間q賦值 *q = e;//當前長度+1 L.length++;}else{//如果分配空間沒有使用完，執行下面操作//取要插入位置的地址 ElemType* q = &(L.elem[i-1]);//如果地址p比插入的地址q大或則等于，就將數據復制到后面一位空間里面，空出地址q的存儲空間 for(ElemType* p = &(L.elem[L.length-1]); p>= q; p--){*(p+1) = *p;} //給地址空間q復制 *q = e;//當前長度+1 L.length++;}return ok;} // 刪除i個位置的數據，數據長度減一,并返回數據 Status ListDelete(SqList& L, int i, ElemType& e){if(i > L.length || i<0){cout<<"你刪除的數據不存在\n\n"<<endl;return error; }else{ElemType* q = &L.elem[i-1];e = *q;q = &L.elem[L.length-1];for(ElemType* p = &L.elem[i-1]; p<= q; p++){*p = *(p+1);}L.length--;cout<<"刪除成功\n\n"<<endl;return ok;} } //合并線性表,將LA和LB合并后的結果替換為LA Status Union(SqList& LA, const SqList& LB){int LA_length = LA.length;int LB_length = LB.length;ElemType e;for(int i=0; i<= LB_length; i++){//獲取LB的第i個位置的數據 Get(LB, i, e);for(int i=0; i<LB_length; i++){//在LA中查詢數據e是否存在，不存在就返回i，存在就返回-1 int index = LocateElem(LA, e);//不為-1就在LA中插入數據 e if(index != -1){ListInsert(LA, ++LA.length, e); }} } cout<<"線性表合并完成, 查看第一個線性表可以查看合并后的數據"<<endl;return ok; } //合并有序線性表,并排序，將結果放有序入LC中 Status MergeList(const SqList& LA, const SqList& LB, SqList& LC){InitList(LC);int i, j, k;i = j = 1;k = 0;ElemType a, b;int la_length = LA.length; int lb_length = LB.length;while((i <= la_length) && (j <= lb_length)){Get(LA, i, a); Get(LB, j, b);if(a <= b){{ListInsert(LC, ++k, a);i++;}}else{ListInsert(LC, ++k, b);j++;}}while(i <= la_length){Get(LA, i++, a);ListInsert(LC, ++k, a);}while(j <= lb_length){Get(LB, j++, b);ListInsert(LC, ++k, b);}} //查詢某個數據e的位置 int LocateElem(const SqList& L, ElemType e){if(L.length == 0){return -1;}for(int i=0; i<L.length; i++){if(L.elem[i] == e){return i+1;}else{return -1;}}} //插入n個數據Status Insert(SqList& L, int n){ElemType e;if(n + L.length > L.listsize){L.elem = (ElemType*)(realloc(L.elem, (LIST_ADD) * sizeof(ElemType)));//如果地址分配失敗，就返回錯誤 if(!L.elem) return error;L.listsize = L.listsize + LIST_ADD;}cout<<"請輸入你要插入的"<<n<<"數據"<<endl;for(int i=L.length; i<n; i++){cin>> L.elem[i];}cout<<"數據插入完成\n\n"<<endl; L.length = L.length + n;return ok;}

3、測試文件test.cpp：

#include <iostream> #include "List.h"/* run this program using the console pauser or add your own getch, system("pause") or input loop *///測試一個線性表功能 int main(int argc, char** argv) {SqList L;cout<<"請輸入你的操作"<<endl;cout<<" 0-----退出\n"<<endl;cout<<" 1-----初始化線性表\n"<<endl;int n;int i;ElemType e;//初始化線性表 InitList(L);while(1){cout<<"請輸入你的操作"<<endl;cin>>n;if(n>1 || n < 0){cout<<"你輸入的有問題，請重新輸入"<<endl;}else{break;}} if(n == 0){cout<<"你已退出"<<endl;exit(flow);}//進入操縱while(1){switch(n){case 0: //銷毀之后重新進行初始化,并退出 DestroyList(L);cout<<"線性表銷毀成功\n\n"<<endl;cout<<"你已退出"<<endl;exit(flow); case 1://重新初始化線性表 if(L.elem){free(L.elem);cout<<"重新初始化成功，原來數據被清空\n\n"<<endl;}InitList(L); break;case 2://查看線性表所有數據 Print(L); break;case 3://數據插入 cout<<"請輸入你要插入的位置和數據\n"<<endl;cin>>i;cin>>e;if(ListInsert(L, i, e)){cout<<"插入成功\n\n"<<endl;} else{cout<<"插入失敗\n\n"<<endl;}break;case 4://刪除功能 cout<<"請輸入你要刪除的位置"<<endl;cin>>i;ListDelete(L, i, e);break;case 5://查詢數據 cout<<"請輸入你要查詢的數據"<<endl;cin>>e;i = LocateElem(L, e);if(i != -1){cout<<"你查詢的數據是第"<<i<<"個位置\n\n"<<endl;}else{cout<<"你查詢的數據不存在\n\n"<<endl; }break;case 6://判斷線性表是否為空 if(!ListEmpty(L)){cout<<"線性表為空表\n\n"<<endl;}else{cout<<"線性表不為空\n\n"<<endl;}break;}cout<<" 0-----退出,并銷毀線性表\n"<<endl;cout<<" 1-----重新初始化線性表\n"<<endl;cout<<" 2-----打印線性表\n"<<endl;cout<<" 3-----插入數據\n"<<endl;cout<<" 4-----刪除某個數據\n"<<endl;cout<<" 5-----查詢數據的位置\n"<<endl;cout<<" 6-----判斷線性表是否為空\n"<<endl;cout<<"請輸入你的操作"<<endl;//控制操作輸入 while(1){//輸入操作方式 cin>>n;cout<<endl;if(n>6 || n < 0){cout<<"你輸入的有問題，請重新輸入"<<endl;}else{break;}} }return 0; }

總結

以上是生活随笔為你收集整理的线性表的C/C++实现（数据结构 严蔚敏版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。