数据结构-改进链表
单链表在很多场合下，是线性表的首选存储结构。然而，它也存在这实现某些基本操作，如求线性表的长度时不如顺序存储结构的缺点。另一方面，由于在链表中，结点之间的关系用指针来表示。则数据元素在线性表中的位序的概念已经淡化，而被数据元素在线性链表中的位置所代替，为此，从实际应用角度出发重新定义线性链表及其基本操作。
定义的辅助宏：
#define OK 1
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NULL 0
#define OVERFLOW -1
typedef int Status;
typedef int ElemType;//假设改进链表中的元素均为整型改进链表的存储结构定义：
//结点类型
typedef struct LNode{ElemType data;struct LNode * next;
}*Link,*Position;
typedef struct{ //链表类型Link head,tail; //头指针与尾指针int len; //表长
}LinkList;分配由p指向的值为e的结点，并返回OK，若分配失败，返回ERROR.
Status MakeNode(Link &p,ElemType e){
//分配由p指向的值为e的结点，并返回OK，若分配失败，返回ERRORp=(LNode *)malloc(sizeof(LNode));if(!p)return ERROR;p->data=e;p->next=NULL;return OK;
}释放p所指结点.
void FreeNode(Link &p){
//释放p所指结点free(p);p=NULL;
}构造一个空的线性链表L，头尾指针指向头结点.
Status InitList(LinkList &L){//构造一个空的线性链表L，头尾指针指向头结点ElemType e;e=-1; //实际应用中此初始化语句需要修改if(!MakeNode(L.head,e)) //开辟头结点return ERROR;L.tail=L.head;L.len=0;return OK;
}销毁线性表L，L不再存在。
Status DestroyList(LinkList &L){//销毁线性表L，L不在存在LNode *p=L.head->next;while(p){L.head->next=p->next;//依次释放第一个结点到最后一个结点所占空间FreeNode(p);p=L.head->next;} FreeNode(L.head);L.head=NULL;L.tail=NULL;L.len=0;return OK;
}将线性表L重置成空表，并释放原链表的结点空间.
Status ClearList(LinkList &L){
//将线性表L重置成空表，并释放原链表的结点空间LNode *p=L.head->next;while(p) {L.head->next=p->next; //依次释放第一个结点到最后一个结点所占空间FreeNode(p);p=L.head->next;} L.tail=L.head; L.len=0;return OK;
}将s所指结点插入在第一个结点之前，头结点后.
Status InsFirst(LinkList &L,Link s){//将s所指结点插入在第一个结点之前，头结点后s->next=L.head->next;L.head->next=s;if(!L.len)L.tail=s;//如果空表，尾指针也改变 L.len++;return OK;
}已知head指向线性表的头结点，删除链表第一个结点并以q返回,如果为空表，q赋空返回ERROR.
Status DelFirst(LinkList &L,Link &q){//已知h指向线性表的头结点，删除链表第一个结点并以q返回,如果为空表，q赋空返回ERRORif(!L.len){q=NULL;return ERROR;} if(L.len==1) //删完为空表尾指针改变L.tail=L.head; q=L.head->next;L.head->next=q->next;q->next=NULL; L.len--;return OK;
}将指针s所指的一串结点连接在线性表L的最后一个结点,改变尾指针和表长.
Status Append(LinkList &L,Link s){//将指针s所指的一串结点连接在线性表L的最后一个结点,改变尾指针和表长 L.tail->next=s;while(L.tail->next){ L.tail=L.tail->next;L.len++;} return OK;
}删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点.
Status Remove(LinkList &L,Link &q){//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点if(!L.len){q=NULL;return ERROR;}LNode *p=L.head;while(p->next!=L.tail)p=p->next;q=L.tail;p->next=NULL;L.tail=p;L.len--;return OK;
}p为第一个结点，s结点插入p结点之前，修改p指向新插入的结点.
Status InsBefore(LinkList &L,Link &p,Link s){//p为一个结点，s结点插入p结点之前，修改p指向新插入的结点LNode *q = L.head;while(q->next && q->next != p)q = q->next;if(!q->next)return ERROR;s->next = p;q->next = s;p = s;++L.len;return OK;
}p为第一个结点，s结点插入p结点之后，修改p指向新插入的结点.
Status InsAfter(LinkList &L,Link &p,Link s){//p为一个结点，s结点插入p结点之后，修改p指向新插入的结点s->next=p->next;p->next=s;p=p->next;L.len++;if(!p->next)L.tail=p;//若插入到表尾 尾指针应该改变return OK;
}p指向第一个结点，用e更新p结点中数据元素的值.
Status SetCurElem(Link &p,ElemType e){//p指向第一个结点，用e更新p结点中数据元素的值if(!p)return ERROR;p->data=e;return OK;
}p指向第一个结点，返回p结点中数据元素的值.
ElemType GetCurElem(Link p){
//p指向第一个结点，返回p结点中数据元素的值if(!p)exit(OVERFLOW);return p->data;
}若为空表，返回TRUE，否则返回FALSE.
Status ListEmpty(LinkList L){
//若为空表，返回TRUE，否则返回FALSEif(L.len)return FALSE;return TRUE;
}返回线性链表L中元素个数.
int ListLength(LinkList L){//返回线性链表L中元素个数return L.len;
}返回线性链表L头结点的位置.
Position GetHead(LinkList L){//返回线性链表L头结点的位置return L.head;
} 返回线性链表最后一个结点的位置.
Position GetLast(LinkList L){//返回线性链表最后一个结点的位置return L.tail;
}p指向一个结点,返回p所指的结点的前驱的位置.
Position PriorPos(LinkList L,Link p){//p指向一个结点,返回p所指的结点的前驱的位置if(!p||p==L.head->next)return NULL;LNode *q=L.head;while(q->next!=p)q=q->next;return q;
}p指向一个结点,返回p所指的结点的后驱的位置 无后继则返回NULL.
Position NextPos(LinkList L,Link p){//p指向一个结点,返回p所指的结点的后驱的位置//无后继则返回NULLreturn p->next;
}返回p指向第i个结点的位置并返回OK，i值不合法返回ERROR.
Status LocatePos(LinkList L,int i,Link &p){//返回p指向第i个结点的位置并返回OK，i值不合法返回ERRORif(i<1||i>L.len){p=NULL;return ERROR;}LNode *q=L.head;int j=0;while(q&&jnext;j++;}p=q;return OK;
} 依次对L中每个元素调用visit()，调用失败则操作失败.
Status ListTraverse(LinkList L,Status (*visit)(ElemType &)){//依次对L中每个元素调用visit()，调用失败则操作失败LNode *p=L.head->next;while(p){if(!visit(p->data))return ERROR;p=p->next;}return OK;
}已知p指向L中某个结点，删除p结点后的结点以q返回 表长减1.
Status DeleteAfter(LinkList &L,Link p,Link &q){//已知p指向L中某个结点，删除p结点后的结点以q返回 表长减1if(!p->next){q=NULL;return ERROR;}if(p==L.head){DelFirst(L,q); return OK;}q=p->next;if(q==L.tail)L.tail=p;p->next=q->next;q->next=NULL; L.len--;return OK;
}返回线性表L中第一个与e满足函数compare（）判定关系的元素的前驱的位置，没有返回NULL；
Status LocateElemPrior(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType),Link &p){//返回线性表L中第一个与e满足函数compare（）判定关系的元素的前驱的位置，没有返回NULL；p=L.head;while(p->next&&!compare(e,p->next->data))p=p->next;if(p->next==NULL){p=NULL;return FALSE;}elsereturn OK;
}返回线性表L中第一个与e满足函数compare（）判定关系的元素位置，没有返回NULL；
Status LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType),Link &p){//返回线性表L中第一个与e满足函数compare（）判定关系的元素位置，没有返回NULL；p=L.head->next;while(p&&!compare(e,p->data))p=p->next;if(!p) { return ERROR;}return OK;
}向链表中插入e，链表依然满足compare（）的顺序.
Status BigEqual(ElemType e1,ElemType e2){if(e1>=e2)return TRUE;return FALSE;
}
Status SmallEqual(ElemType e1,ElemType e2){if(e1<=e2)return TRUE;return FALSE;
}
Status Equal(ElemType e1,ElemType e2){if(e1==e2)return TRUE;return FALSE;
}
Status ListInsert_Sorted(LinkList &L,ElemType e,Status (*compare)(ElemType,ElemType)){//向链表中插入e，链表依然满足compare（）的顺序,当cmp为SamllEqual时为升序，即将e插入到//第一个大于等于e的元素之前，当cmp为BigEual时为降序，将e插入到第一个小于等于e的元素前LNode *p,*s;if(!MakeNode(s,e))exit(OVERFLOW);LocateElem(L,e,compare,p);if(p)InsBefore(L, p, s);elseAppend(L,s); //未找到时插入到表尾结点之后return OK;
}依次输出链表L中的各个元素以及表长.
void PrintList_L(LinkList L){
//依次输出链表L中的各个元素以及表长printf("表长：%d\n",L.len);if(!L.len)printf("空表\n");else{LNode *p=L.head->next;while(p){OutputElem(p->data);p=p->next;}}
}已知La与Lb有序排列，归并LaLb到Lc，Lc也有序排列.
Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,Status (*compare)(ElemType,ElemType)){//已知La与Lb有序排列，归并LaLb到Lc，Lc也有序排列//将非降链表La与Lb归并为非降链表Lc，原链表销毁，链表带头结点//指针pa pb pc分别遍历三表，比较当前元素，小的插入Lc中pc后的位置。if(!InitList(Lc)) //存储空间分配失败return ERROR;Link ha=GetHead(La),hb=GetHead(Lb),q,pa,pb; //ha和hb分别指向La和Lb的头结点ElemType a,b;pa=NextPos(La,ha); //pa和pb分别指向La和Lb中当前结点pb=NextPos(Lb,hb);while(pa&&pb){ //La和Lb均非空a=GetCurElem(pa); //a和b为两表中当前比较元素b=GetCurElem(pb);if(compare(a,b)){DelFirst(La,q);Append(Lc,q);pa=NextPos(La,ha);}else{DelFirst(Lb,q);Append(Lc,q);pb=NextPos(Lb,hb);}}if(pa) //链接La中剩余结点Append(Lc,pa);else //链接Lb中剩余结点Append(Lc,pb);FreeNode(ha); //释放La和Lb的头结点FreeNode(hb);return OK;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！