1、线性表的顺序存储
#include <stdio.h> #include <malloc.h> typedef int ElementType; #define MAXSIZE 10 struct listStr { int data[MAXSIZE]; int last; }; typedef struct listStr List; List* makeEmptyTest();//初始化,建立空表 int findElementTest( ElementType X, List* ptrL);//查找元素X,返回对应数组下标 void insertElementTest(ElementType X, int i, List *ptrL);//在第i个位置(对应a[i-1])插入元素X void deleteElementTest(int i,List *ptrL);//删除第i个元素,即a[i-1] void printListTest(List* ptrL); int main() { List *ptrL=NULL;//表的长度L.last+1 or ptrL->last+1 ptrL=makeEmptyTest(); insertElementTest(1,1,ptrL); insertElementTest(2,2,ptrL); insertElementTest(3,3,ptrL); printListTest(ptrL); printf("findElementTest: %d\n",findElementTest(2,ptrL)); deleteElementTest(1,ptrL); printListTest(ptrL); } List* makeEmptyTest()//初始化,建立空表 { List* ptrL=(List*)malloc(sizeof(List)); ptrL->last = -1;//数组下标从0开始 return ptrL; } int findElementTest( ElementType X, List* ptrL)//查找元素X,返回对应数组下标 { int i=0; while(i <= ptrL->last && ptrL->data[i] != X) { i++; } if(i>ptrL->last) { return -1;//没找到 } else { return i; } } void insertElementTest(ElementType X, int i, List *ptrL)//在第i个位置(对应a[i-1])插入元素X { int j; if(ptrL->last == (MAXSIZE-1)) { printf("list is full...\n"); return; } if(i<1 || i>ptrL->last+2) { printf("location error...\n"); return; } for(j=ptrL->last;j>=i-1;j--)//将a[last]一直到a[i-1]往后移动一位,空出a[i-1],即第i个位置 { ptrL->data[j+1]=ptrL->data[j]; } ptrL->data[i-1]=X; ptrL->last++; return; } void deleteElementTest(int i,List *ptrL)//删除第i个元素,即a[i-1] { int j; if( i<1 || i>(ptrL->last+1) ) { printf("not exist %d element...\n",i); return; } for(j=i;j<=ptrL->last;j++) { ptrL->data[j-1]=ptrL->data[j]; } ptrL->last--; return; } void printListTest(List* ptrL) { int j; for(j=0;j<=ptrL->last;j++) { printf("%d,",ptrL->data[j]); } return; }
2、线性表的链式存储
#include <stdio.h> #include <malloc.h> typedef int ElementType; typedef struct Node { ElementType data; struct Node *next; } List; int lengthList(List *ptrL); List* findKth( int K, List* ptrL); List* findValue( int X, List* ptrL); List* insertElementTest(ElementType X, int i, List *ptrL); List* deleteElementTest(int i,List *ptrL); void printListTest(List* ptrL); int main() { List *ptrL=NULL; ptrL=insertElementTest(1,1,ptrL); ptrL=insertElementTest(2,2,ptrL); ptrL=insertElementTest(3,3,ptrL); printListTest(ptrL); deleteElementTest(2,ptrL); printListTest(ptrL); } int lengthList(List *ptrL) { List*pTmp=ptrL; int j=0; while(pTmp) { pTmp=pTmp->next; j++; } return j; } List* findKth( int K, List* ptrL) { List *pTmp=ptrL; int i=1; while(pTmp!=NULL && i<K) { pTmp=pTmp->next; i++; } if(i==K) { return pTmp; } else { return NULL; } } List* findValue( int X, List* ptrL) { List *pTmp=ptrL; while(pTmp!=NULL && pTmp->data!=X) { pTmp=pTmp->next; } return pTmp; } List* insertElementTest(ElementType X, int i, List *ptrL) { List *p, *s; if(i==1) { s=(List*)malloc(sizeof(List)); s->data=X; s->next=ptrL; return s; } p=findKth(i-1,ptrL); if(p==NULL) { printf("i error...\n"); return NULL; } else { s=(List*)malloc(sizeof(List)); s->data=X; s->next=p->next; p->next=s; return ptrL; } } List* deleteElementTest(int i,List *ptrL) { List *p,*s; if(i==1) { s=ptrL; if(ptrL!=NULL) { ptrL=ptrL->next; } else { return NULL; } free(s); return ptrL; } else { p=findKth(i-1,ptrL); if(p==NULL) { printf("%d node not exist...\n",i-1); return NULL; } else if(p->next==NULL) { printf("%d node not exist...\n",i); return NULL; } else { s=p->next; p->next=s->next; free(s); return ptrL; } } } void printListTest(List* ptrL) { List* pTmp; for(pTmp=ptrL;pTmp!=NULL;pTmp=pTmp->next) { printf("%d,",pTmp->data); } return; }
线性表顺序存储
/****************************************************** *线性表—顺序存储 ******************************************************/ #include <iostream> using namespace std; #define MAXSIZE 20 //数组最大长度 typedef int ElemType;//数组类型 typedef struct { ElemType data[MAXSIZE]; //数组,最大长度MAXSIZE int length; //线性表当前长度 }SqList; #define OK 1 #define ERROR 0 /***************************************************** *功能:获取元素,获得线性表第i个位置元素,对应数组下标i-1 *L[in]:线性表 *i[in]:第i个位置 *e[out]:第i个位置元素数值 ******************************************************/ int GetElem(SqList L, int i, ElemType*e) { if (L.length < 1 || i<1 || i>L.length) { return ERROR; } *e = L.data[i - 1]; return OK; } /************************************************************ *功能:插入,在线性表第i个位置插入新元素e,下标i-1为新元素e,后面元素后移一位 *L:线性表 *i:第i个位置 *e:新元素 *************************************************************/ int ListInsert(SqList* L, int i, ElemType e) { if (L->length == MAXSIZE)//表满,无法插入 { return ERROR; } if ((i<1) || (i>(L->length+1))) { return ERROR; } if (i == L->length + 1)//插在最后一个位置,不需要移动元素,直接插入 { L->data[L->length] = e; L->length++; return OK; } for (int k = L->length - 1; k >= i - 1; k--) { L->data[k+1] = L->data[k]; } L->data[i - 1] = e; L->length++; return OK; } /***************************************************** *功能:线性表删除 *L[in]:线性表 *i[in]:第i个数据元素 *e[out]:第i个数据元素数值 ******************************************************/ int deleteList(SqList* L, int i, ElemType* e) { if (L->length<1 || L->length>MAXSIZE) { return ERROR; } if (i<1 || i>L->length) { return ERROR; } *e = L->data[i - 1];//取出第i个元素数值 if (i == L->length)//删除最后一个元素,不需要移动元素 { L->length--; return OK; } for (int k = i; k < L->length; k++) { L->data[k-1] = L->data[k]; } L->length--; return OK; } int main() { SqList listTest; int length = 10; listTest.length = length; for (int i = 0; i < listTest.length; i++) { listTest.data[i] = i; } //输出列表 for (int i = 0; i < length; i++) { cout << listTest.data[i] << ", "; } //GetElem函数测试 int testNum = 5;//获得第5个元素数值 ElemType elem = 0; int status = 0; status = GetElem(listTest, testNum, &elem); if (status == OK) { cout << endl << elem << endl; } else { cout << "GetElem error..." << endl; } //ListInsert函数测试 ElemType elemInsert = 100; status = ListInsert(&listTest, testNum, elemInsert); if (status == OK) { //输出列表 for (int i = 0; i < listTest.length; i++) { cout << listTest.data[i] << ", "; } } else { cout << "ListInsert error..." << endl; } //deleteList函数测试 ElemType numDel = 0; status = deleteList(&listTest, testNum, &numDel); if (status == OK) { //输出列表 cout << endl; for (int i = 0; i < listTest.length; i++) { cout << listTest.data[i] << ", "; } } else { cout << endl << "deleteList error" << endl; } return 0; }