首页 > 代码库 > 数据结构-线性表
数据结构-线性表
线性表（List）：n个数据的有限集合
1. 顺序结构：用一段地址连续的储存单元依次存储线性表的数据元素
结构代码：
1 #define MAXSIZE 20 //储存空间初始分配量 2 typedef int ElemType; //根据实际情况，这里假设为int3 typedef struct4 {5 ElemTyoe data[MAXSIZE] ; //数组存储数据元素，最大值为MAXSIZE6 int length=0; //线性表长度7 }SqList;
三个属性：存储空间的起始位置（数组data）线性表的最大存储容量（最大长度MAXSIZE）、线性表的当前长度（length）
地址计算：对于第i个元素ai的存储位置可以由a1推出，若一个数据元素占用c个存储单元，则LOC（ai）= LOC( a1)+( i-1 )*c
获取元素：
1 //操作：用e返回L中第i个元素的值2 typedef int Status3 Status GetElem(Sqlist l, int i, ElemType *e)4 {5 if(L.length==0||i<1||i>L.length)6 return 0;7 *e=L.data[i-1];8 return 1;9 }
插入元素：
1 //操作：在L中第i个位置之前插入新的元素e 2 Status ListInsert(Sqlist *L,int i,ElemType e) 3 { 4 int k; 5 if(L->length==MAXSIZE)//线性表已满 6 return 0; 7 if(i<1||i>L->length+1)//当i不在范围 8 return 0; 9 if(i<=L->length)//插入位置以后后移10 {11 for(k=L->length-1;k>=i-1;k--)12 L->data[k+1]=L->data[k];13 }14 L->data[i-1]=e;15 l->length++;16 return 1;17 }
删除元素：
1 //操作：删除L的第i个元素，并用e返回其值 2 Status ListDelete(Sqlist *L,int i,ElemType *e) 3 { 4 int k; 5 if(L->length==0)//线性表为空 6 return 0; 7 if(i<1||i>L->length)//删除位置不正确 8 return 0; 9 *e=L->[i-1];10 if(i<L->length)11 {12 for(k=i;k->length;k++)//后继元素前移13 L->data[k-1]=L->data[k];14 }15 L->length--;16 return 1;17 }
完整实现：
1 //顺序链表实现 2 #include<iostream> 3 using namespace std; 4 #define MAXSIZE 20 //储存空间初始分配量 5 typedef int ElemType; //根据实际情况，这里假设为int 6 typedef struct 7 { 8 ElemType data[MAXSIZE] ; //数组存储数据元素，最大值为MAXSIZE 9 int length=0; //线性表长度 10 } Sqlist; 11 Sqlist s;//为求简便输出使用全局变量 12 //操作：用e返回L中第i个元素的值 13 typedef int Status; 14 void print() 15 { 16 cout << "Item: "; 17 for (int i = 0; i < s.length; i++) 18 cout << s.data[i] << ‘ ‘; 19 cout << "Length: " << s.length << endl; 20 } 21 Status GetElem(Sqlist L, int i, ElemType *e) 22 { 23 if (L.length == 0 || i < 1 || i > L.length) 24 return 0; 25 *e = L.data[i - 1]; 26 return 1; 27 } 28 //操作：在L中第i个位置之前插入新的元素e 29 Status ListInsert(Sqlist *L, int i, ElemType e) 30 { 31 int k; 32 if (L->length == MAXSIZE) //线性表已满 33 return 0; 34 if (i < 1 || i > L->length + 1) //当i不在范围 35 return 0; 36 if (i <= L->length) 37 { 38 for (k = L->length - 1; k >= i - 1; k--) 39 L->data[k + 1] = L->data[k]; 40 } 41 L->data[i - 1] = e; 42 L->length++; 43 print(); 44 return 1; 45 } 46 //操作：删除L的第i个元素，并用e返回其值 47 Status ListDelete(Sqlist *L, int i, ElemType *e) 48 { 49 int k; 50 if (L->length == 0) //线性表为空 51 return 0; 52 if (i < 1 || i > L->length) //删除位置不正确 53 return 0; 54 *e = L->data[i - 1]; 55 if (i < L->length) 56 { 57 for (k = i; k < L->length; k++) //后继元素前移 58 L->data[k - 1] = L->data[k]; 59 } 60 L->length--; 61 print(); 62 return 1; 63 } 64 void list() 65 { 66 cout << "Options: "<<endl<< "1.Find"<<endl << "2.Insert"<<endl << "3.Delete"<<endl; 67 } 68 int main() { 69 cout << "The implent of list" << endl; 70 cout << "length:" << endl; 71 cin >> s.length; 72 cout << "The item of list:" << endl; 73 for (int i = 0; i < s.length; i++) 74 cin >> s.data[i]; 75 print(); 76 while (1) 77 { 78 int choose; 79 list(); 80 cin>>choose; 81 if (choose == 1) { 82 int elem, i; 83 cout << "Find:"<<endl; 84 cin >> i; 85 GetElem(s, i, &elem); 86 cout << elem << endl; 87 } 88 if (choose == 2) { 89 int i, e; 90 cout << "Insert:"<<endl; 91 cin >> i >> e; 92 ListInsert(&s, i, e); 93 } 94 if (choose == 3) { 95 int i, e; 96 cout << "Delete:"<<endl; 97 cin >> i; 98 ListDelete(&s, i, &e); 99 cout << e << "has been deleted." << endl;100 }101 }102 }
数据结构-线性表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。