首页 > 代码库 > 线性表
线性表
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=http://www.mamicode.com/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=http://www.mamicode.com/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; }
线性表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。