1.线性表顺序结构 定义(一) 元素所占空间和表长合并为C语言的一个结构类型 #define maxleng i typedef struct Elem Type elem( maxlengI:∥下标.0,1,, maxing-1 int length ∥表长 i Sqlist 其中: typedef-别名定义, Sqlist-结构类型名 La--结构类型变量名 La length-表长 La elem[0]----al La elem[ La length-1]---an 定义(二) 预先分配一个适当的空间,当发生溢出时在扩充。 #define LIST INIT SIZe 100 /*初始分配的适当空间* #define LIS iNcrement 10 /*每次发生溢出时扩充的增量* typedef struct Elem Type*elem;∥存储空间基地址 int length ∥表长 int listsize,∥当前分配的存储容量 ∥(以 sizeof( Elem Type)为单位 Sqlist Lb 其中: typedef-别名定义, Sqlist-结构类型名 Lb--结构类型变量名 Lb length-表长 Lb elem[0]----bl Lb elem[ Lb length-1]---by 算法举例(按第二种定义结构) #include stdio h" # define list Init size100/首次分配连续存储单元的大小, 可存储 LIST INIT SIZE个元素* # define listincrement10/每当发生溢出时,扩充的增量* # define cⅤ ERFLOV-2 #define OK #define error o
1．线性表顺序结构 定义（一） 元素所占空间和表长合并为 C 语言的一个结构类型： #define maxleng 100 { typedef struct { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1 int length； //表长 } SqList； SqList La； .......... } 其中：typedef---别名定义，SqList----结构类型名 La----结构类型变量名 La.length---表长 La.elem[0]----a1 La.elem[La.length-1]---an 定义（二） 预先分配一个适当的空间，当发生溢出时在扩充。 #define LIST_INIT_SIZE 100 /*初始分配的适当空间*/ #define LISTINCREMENT 10 /*每次发生溢出时扩充的增量*/ typedef struct { ElemType *elem；//存储空间基地址 int length； //表长 int listsize; //当前分配的存储容量 //（以 sizeof(ElemType)为单位 } SqList； SqList Lb； 其中：typedef---别名定义，SqList----结构类型名 Lb----结构类型变量名 Lb.length---表长 Lb.elem[0]----b1 Lb.elem[Lb.length-1]---bn 算法举例（按第二种定义结构）： #include "stdio.h" #define LIST_INIT_SIZE 100 /*首次分配连续存储单元的大小， 可存储 LIST_INIT_SIZE 个元素*/ #define LISTINCREMENT 10 /*每当发生溢出时，扩充的增量*/ #define OVERFLOW -2 #define OK 1 #define ERROR 0
typedef int ElemType; /假定数据元素为int* typedef struct sqlist ElemType*elem /连续存储单元首地址 int length; /线性表长度 int listsize /最大容量:连续存储单元可存储元素数 /“ Sqlist为结构类型,用其说明的变量在程序中作为线性表 /率容率本本*本******************幸*** 功能:初始化线性表,包括: 给线性表分配连续存储空间 设定连续空间可存放最大元素数 设置线性表初始表长度为零 输入:被初始化的线性表指针L 输出:成功时返回OK 水水常称*客水客水本客*客布水市水常水水水称称水凇常客涂*水客水水客容水客水客水客水 /分配初始连续空间* L->elem( Elem Type *)malloc(LIST INIT SIZE*sizeof( Elem Type); if(! L->elem)exit(OVERFLOW) L->length=0 /*初始表长度为零* L->listsize=LIST INIT SIZE /*设定连续空间可存放最大元素数* /***亲率幸本***幸本**亲*率本幸本*****亲率本 ★功能:线性表插入操作,将某数据元素插入到线性表 的第i个数据元素之前 输入:线性表指针L、位置i、待插入的数据元素e 输出:成功时返回OK 水**客水*水水水**水客水*亦水客*客水水容凇客水*水客**客水涂水本客水水客水*水*水*客**客 int insert sq(sqlist*L, int i, Elem Type e f(i<1‖p>L> length+1) return ERROR;/*i的合法取值为1至n+1* (L-> ength>=L-> elistsize)/*溢出时扩充* Elem Type newbase newbase=(Elem Type *)realloc(L->elem (L->listsize+LISTINCREMENT)*sizeof( Elem Type); if (newbase==NULL) exit(OVERFLOW) L->elem=newbase
typedef int ElemType; /*假定数据元素为 int*/ typedef struct SqList { ElemType *elem; /*连续存储单元首地址*/ int length; /*线性表长度*/ int listsize; /*最大容量：连续存储单元可存储元素数*/ } SqList; /*SqList 为结构类型，用其说明的变量在程序中作为线性表*/ /**************************************************** ** 功能：初始化线性表，包括： ** ** 给线性表分配连续存储空间 ** ** 设定连续空间可存放最大元素数 ** ** 设置线性表初始表长度为零 ** ** 输入：被初始化的线性表指针 L ** ** 输出： 成功时返回 OK ** ****************************************************/ int init_sq(struct SqList *L) { /*分配初始连续空间*/ L->elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L->elem) exit(OVERFLOW); L->length=0; /*初始表长度为零*/ L->listsize=LIST_INIT_SIZE; /*设定连续空间可存放最大元素数*/ return OK; } /********************************************************** ** 功能：线性表插入操作，将某数据元素插入到线性表 ** ** 的第 i 个数据元素之前 ** ** 输入：线性表指针 L、位置 i、待插入的数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int insert_sq(SqList *L,int i, ElemType e) { int j; if (i<1 || i>L->length+1) return ERROR; /*i 的合法取值为 1 至 n+1*/ if (L->length>=L->listsize) /*溢出时扩充*/ { ElemType *newbase; newbase=(ElemType *) realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(ElemType)); if (newbase==NULL) exit(OVERFLOW); L->elem=newbase;
L->listsize+=LIS TINCREMENT for(=L-> length-1j>=i-1j-)/向后移动元素,空出第i个元素的分量 elem i-l]’/ 新元素插入 L->length++ /*线性表长度加1* return OK /*****本*容*本*****客春**幸*幸本布*****本幸*率*****本** *功能:线性表删除操作,删除线性表的第i个数据元素☆ **输入:线性表指针L、位置i 输出:成功时返回OK int delete sq(sqlist *L, int i) Int J; if (i<l l i>L->length) return ERROR; for(=ij<L> length: j++)/向前移动元素* ->elem[j-1=L->elem[I: L->length-- /*线性表长度减1* eturn o 称水*客水客水*水水客水水*水*客客客水客客水水*水水水客*称水*水客水*水客客水幸 ★功能:显示线性表的所有数据元素 输入:线性表L 输出:无 水水涂*凇水本客水水市客水水称水布水客 void display( SqList L) for(i=0; i<L length; i++) printf("\na[ %d]=%d",i+1, L elem(iD: Sqlist La corsarO init sq(&la /*初始化线性表La,实参为线性表La的指针* Insert sq&La1,1);/*数据元素1插入到线性表La的第1个数据元素之前*
L->listsize+=LISTINCREMENT; } for(j=L->length-1;j>=i-1;j--) /*向后移动元素，空出第 i 个元素的分量 elem[i-1]*/ L->elem[j+1]=L->elem[j]; L->elem[i-1]=e; /*新元素插入*/ L->length++; /*线性表长度加 1*/ return OK; } /********************************************************** ** 功能：线性表删除操作，删除线性表的第 i 个数据元素 ** ** 输入：线性表指针 L、位置 i ** ** 输出： 成功时返回 OK ** **********************************************************/ int delete_sq(SqList *L,int i) { int j; if (i<1 || i>L->length) return ERROR; for(j=i;j<L->length;j++) /*向前移动元素*/ L->elem[j-1]=L->elem[j]; L->length--; /*线性表长度减 1*/ return OK; } /********************************************************** ** 功能：显示线性表的所有数据元素 ** ** 输入：线性表 L ** ** 输出： 无 ** **********************************************************/ void display(SqList L) { int i; for (i=0;i<L.length;i++) printf("\na[%d]=%d",i+1,L.elem[i]); } main() { SqList La; clrscr(); init_sq(&La); /*初始化线性表 La, 实参为线性表 La 的指针*/ insert_sq(&La,1, 1); /*数据元素１插入到线性表 La 的第１个数据元素之前*/
Insert sq&La1,2);/*数据元素2插入到线性表La的第1个数据元素之前* insert so(&La1,3);/*数据元素3插入到线性表La的第1个数据元素之前* Insert_sq(&La,4,5);/数据元素5插入到线性表La的第4个数据元素之前* delete sq(&La,1),/*删除线性表La的第1个数据元素* display (La) /*显示线性表La的数据元素* 2单链表 算法举例(带表头结点的单链表) typedef int Elem Type typedef struct LNode f Elem Type data struct LNode *next. A LNode, *LinkList /*可理解为定义两个类型 LNode 结构类型 Linklist 结点指针类型,指向结点 由于头指针是结点指针,所以该类型变量可定义为链表 LNode*p等价于 LinkList p* 水本**客*水常涂本客水水涂水水水水亦**客水*水本客水 功能:初始化单链表,产生头结点 输入:无 ★输出:成功时返回头结点指针 水本水* LinkList Listlnit( L Node Linklist) malloc(sizeof( LNode);倖*产生头结点* s->data=0: S->next-NULL return s /*返回头结点指针 /*幸**幸**幸*****市**春**家*率 功能:线性表插入操作,将某数据元素插入到单链表 的第i个数据元素之前 输入:单链表的头指针L、位置i、待插入的数据元素e 输出:成功时返回OK int ListInsert(LinkList L, int 1, Elem Type e)
insert_sq(&La,1, 2); /*数据元素 2 插入到线性表 La 的第１个数据元素之前*/ insert_sq(&La,1, 3); /*数据元素 3 插入到线性表 La 的第１个数据元素之前*/ insert_sq(&La,4 , 5); /*数据元素 5 插入到线性表 La 的第 4 个数据元素之前*/ delete_sq(&La,1); /*删除线性表 La 的第１个数据元素*/ display(La) /*显示线性表 La 的数据元素*/; } 2 单链表 算法举例（带表头结点的单链表）： typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; /*可理解为定义两个类型: LNode ----- 结构类型; LinkList ----- 结点指针类型，指向结点, 由于头指针是结点指针，所以该类型变量可定义为链表 LNode *p 等价于 LinkList p */ /**************************************************** ** 功能：初始化单链表，产生头结点 ** ** 输入：无 ** ** 输出： 成功时返回头结点指针 ** ****************************************************/ LinkList ListInit() { LNode *s; s=(LinkList) malloc(sizeof(LNode)); /*产生头结点*/ s->data=0;s->next=NULL; return s; /*返回头结点指针*/ } /********************************************************** ** 功能：线性表插入操作，将某数据元素插入到单链表 ** ** 的第 i 个数据元素之前 ** ** 输入：单链表的头指针 L、位置 i、待插入的数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int ListInsert(LinkList L,int i, ElemType e) {
LNode* p, s J p=(LNode )L /*p指向链表头结点* while(p && j<i-1) (p=p->next; ++3: 3 /*执行i-1次定位第i-1个结点* f(plj>i-1) return ERROR;/p为NULL时表示没有第i1个结点 j>-1表示i<=0时插入序号错* (LinkList) malloc(sizeof(LNode)) S->next=p->next p->next=s, /*s所指新结点插入p所指第i-1个结点之后 return OK. 功能:线性表删除操作,删除单链表的第i个结点 输入:单链表的头指针L、位置i 输出:成功时返回OK 本本李*率***幸*李*本*亲率本本事本春**率幸本幸率幸春率本幸*率*/ int List Delete( LinkList L, int 1) LNode *p, *q; IntJ; p=( LNode*)L;/*p指向链表头结点* while(p->next & j<i-1) 行i1次,使p定位第i1个结点 p->next指向结点第i个结点, search for ith node* ((p-next)>i-1)return ERROR; 功能:读取线性表第i个结点的值 ☆输入:单链表的头指针L、位置i ★输出:成功时返回OK、通过指针e返回第i个结点的值* 失败返回 ERROR Int p=( LNode*)L->next;,/p指向链表第1个结点* while(p&&j<i) {p=p->next++j;}/*执行i-l次,使p定位第i个结点 if(pll>1) return ERROR;
LNode *p,*s; int j; p=(LNode *) L; /*p 指向链表头结点*/ j=0; while (p && j<i-1) {p=p->next;++j;} /* 执行 i-1 次定位第 i-1 个结点 */ if (!p || j>i-1) return ERROR; /*p 为 NULL 时表示没有第 i-1 个结点 j>i-1 表示 i<=0 时插入序号错*/ s=(LinkList) malloc(sizeof(LNode)); s->data=e; s->next=p->next;p->next=s; /*s 所指新结点插入 p 所指第 i-1 个结点之后*/ return OK; } /********************************************************** ** 功能：线性表删除操作，删除单链表的第 i 个结点 ** ** 输入：单链表的头指针 L、位置 i ** ** 输出： 成功时返回 OK ** **********************************************************/ int ListDelete(LinkList L,int i) { LNode *p,*q; int j; p=(LNode *) L; /*p 指向链表头结点*/ j=0; while (p->next && j<i-1) {p=p->next;++j;} /* 执行 i-1 次，使 p 定位第 i-1 个结点 */ p->next 指向结点第 i 个结点, search for ith node*/ if (!(p->next)||j>i-1) return ERROR; q=p->next;p->next=q->next; free(q); return OK; } /********************************************************** ** 功能：读取线性表第 i 个结点的值 ** ** 输入：单链表的头指针 L、位置 i ** ** 输出： 成功时返回 OK、通过指针 e 返回第 i 个结点的值 ** ** 失败返回ＥＲＲＯＲ ** **********************************************************/ int GetElem(LinkList L,int i, ElemType *e) { LNode *p,*s; int j; p=(LNode *) L->next; /*p 指向链表第 1 个结点*/ j=1; while (p && j<i) {p=p->next;++j;} /* 执行 i-1 次，使 p 定位第 i 个结点 */ if (!p||j>i) return ERROR;