线性表(三)

?

线性表(一)?

?

线性表(二)

线性表的链式表示和实现

线性表的顺序存储可以随机存取表中任一元素，缺点是在做插入或删除操作时，需要移动大量的元素。

线性表的链式存储不要求逻辑上相邻的元素在物理位置上也相邻，在做插入或删除操作时，不需要移动元素，但也失去了随机存取的特点。

1 线性链表

用一组任意的存储单元存储线性表的数据元素。整个链表的存取必须从头指针开始，头指针指向链表的第一个结点（即第一个数据元素的存储映像）的存储位置，最后一个元素没有直接后继，则线性链表中最后一个结点的指针为NULL。

上图为带头结点的非空单链表

/*带有头指针的单链表*/#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0typedef int elemType;typedef struct LNode{elemType data;struct LNode *next;}LNode,*linkNode;typedef struct{linkNode head;int length;} linkList;/*创建结点，分配内存*/void makeNode(linkNode *p,elemType e){*p = (linkNode)malloc(sizeof(LNode));if(!(*p)){printf("空间分配失败!");exit(0);}(*p)->data = e;return;}/*释放结点空间*/void freeNode(linkNode *p){free(*p);*p = NULL;}/*取头结点*/linkNode getHead(linkList *L){return L->head;}/*取当前结点p的后继结点*/linkNode getNext(linkNode p){return p->next;}/*判断当前链表是否为空链表*/int listEmpty(linkList *L){return getHead(L)->next == NULL ? 1: 0;}/*根据序号，获得对应的结点元素*/linkNode getElem(linkList *L,int i){if(i<0||i>L->length+1){printf("查找的结点不存在!");exit(0);}else{int j = 1;linkNode e = getHead(L);while(j< i && e){e = e->next;j++;}return e;}}/*初始化链表*/void initList(linkList *L){linkNode p = (linkNode)malloc(sizeof(LNode));if(p){p->next=NULL;L->length = 0;L->head = p;printf("空间分配成功!\n");}else{printf("空间分配失败!\n");}}/*清空链表*/void clearList(linkList *L){linkNode p = getHead(L);linkNode q;while(p->next == NULL){q = p;p = p->next;freeNode(&q);}p->next = NULL;L->length = 0;return;}/*销毁链表*/void destroyList(linkList *L){clearList(L);freeNode(&L->head);return;}/*在指定位置插入元素*/void listInsert(linkList *L,int i,elemType e){linkNode p = getElem(L,i);linkNode s;makeNode(&s,e);s->next = p->next;p->next = s;L->length++;return;}/*删除指定位置的元素*/void listDelete(linkList *L,int i,elemType e){linkNode p = getElem(L,i);linkNode q = p->next;p->next = q->next;e = q->data;freeNode(&q);L->length--;return;}/*遍历链表*/void listTraverse(linkList *L,void(*visit)(elemType)){linkNode p = L->head->next;int j;while(p != NULL){visit(p->data);p = p->next;}printf("\n");return;}void visit(elemType e){printf("%d ",e);}int compare(elemType a,elemType b){return a-b;}int main(){linkList LA;initList(&LA);int i=1;for(i;i<=5;i++){listInsert(&LA,i,i*3);}listTraverse(&LA,visit);elemType e;listDelete(&LA,2,e);listTraverse(&LA,visit);clearList(&LA);listTraverse(&LA,visit);return 0;}

?