2022年数据结构链表操作 .pdf

/* * 数据结构链表等操作 * */#include #include usingnamespace std; /* 单链表节点结构*/typedef struct NodeType char elem; NodeType *next; Node; /* 双链表节点结构*/typedef struct DNodeType char elem; DNodeType *next; DNodeType *prev; DNode; /*=*/* 创建链表*/Node * CreateList(Node *head) if (NULL = head)/ 分配头节点空间 head=(Node*)malloc(sizeof(Node), head-next=NULL; Node *current=head , *temp; char ch; while( 1) coutch; if ( # = ch) /*# 结束输入 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - break; temp=(Node *) malloc ( sizeof(Node) ); temp-elem=ch; temp-next=NULL; current-next=temp; /* 当前节点的后驱指向新节点*/ current=temp; /* 当前节点为链表尾节点*/ return head; /*=*/* 输出链表*/void PrintList(Node *head) Node * current=head-next; coutelem) coutsetw(5)elem; current=current-next; coutnext; /* 当前节点 */ Node *prev=head; /* 前驱节点 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - Node *temp; /* 过渡节点 */while(current) /* 移动至尾节点*/ prev=current; current=current-next; temp=(Node*) malloc( sizeof(Node) ); temp-elem=elem; temp-next=NULL; prev-next=temp; /* 尾节点的后驱指向新节点*/return head; /*=*/* 删除节点 */Node *DeleteNode(Node *head,char elem) if (NULL = head | NULL = elem) return head; if (NULL = head-next) return head; Node *prev,*current; prev=head; current=head-next; while(current) if (current-elem = elem) /* 匹配节点元素*/ prev-next=current-next; /* 前驱节点的后驱指向当前节点的下一个节点 */ free(current); /* 释放当前节点*/return head; prev=current; current=current-next; /* 移动至下一个节点*/名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - return head; /*=*/* 单链表逆置 */Node *ReverseList(Node *head) if (NULL = head) return head; if (NULL = head-next) return head; if (NULL = head-next-next) return head; Node *curr=head-next; /* 当前节点 */ head-next=NULL; Node *temp; while(curr) temp=curr-next; /* 暂存下一个节点*/* 把当前节点插入到head 节点后 */ curr-next=head-next; head-next=curr; curr=temp; /* 移动至下一个节点*/ return head; /*=*/* 求中间节点 */Node * MiddleNode(Node *head) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - if (NULL = head) return head; if (NULL = head-next) return head-next; Node *p1,*p2; p1=head; p2=head; while(p2-next) /*p2节点移动2 个节点位置 */ p2=p2-next; if (p2-next) /* 判断p2 后驱节点是否存在，存在则再移动一次 */ p2=p2-next; /*p1节点移动1 个节点位置 */ p1=p1-next; return p1; /*=*/* 合并有序单链表*/Node * MergeList(Node * h1,Node * h2) if (NULL = h1 | NULL = h2) return h1; if (NULL = h1-next ) return h2; if (NULL = h2-next) return h1; Node * curr1,*curr2,*prev1,*temp; prev1=h1; /* 链表 1 的前驱节点 */ curr1=h1-next; /* 链表 1 的当前节点 */ curr2=h2-next; /* 链表 2 的当前节点 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - temp=h2; while(curr2) while(curr1 & curr1-elem elem)/* 链表 1 指针移动至大或等于链表2 当前元素的位置*/ prev1=curr1,curr1=curr1-next; /* 在链表 1 中插入链表2 的当前元素 */ temp=curr2-next;/* 暂存链表2 的下一个节点*/ prev1-next=curr2; curr2-next=curr1; /* 链表 1 移动至新节点*/ curr1=curr2; /* 链表 2 移动至下一个节点*/ curr2=temp; return h1; /*=*/* 创建双链表 */DNode * DoubleList(DNode *head) if (NULL = head)/ 分配头节点空间 head=(DNode*)malloc(sizeof(DNode) , head-prev=NULL , head-next=NULL; DNode *current=head , *temp; char ch; while( 1) coutch; if ( # = ch) /*# 结束输入 */break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - temp=(DNode *) malloc ( sizeof(DNode) ); temp-elem=ch; temp-next=NULL; current-next=temp; /* 当前节点的后驱指向新节点*/ temp-prev=current; /* 新节点的前驱指向当前节点*/ current=temp; /* 当前节点为链表尾节点*/ return head; /*=*/* 输出双链表 */void PrintDoubleList(DNode *head) if (NULL = head) return; DNode * p; p=head; coutnext) p=p-next; if (p-elem) coutsetw(5)elem; coutprev) if (p-elem) coutsetw(5)elem; p=p-prev; /*=名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - =*/* 创建循环链表 */Node* CycleList(Node *head) if (NULL = head)/* 分配头节点空间*/ head=(Node*)malloc(sizeof(Node),head-next=NULL; Node *current=head , *temp; char ch; while( 1) coutch; if ( # = ch) /*# 结束输入 */break; temp=(Node *) malloc ( sizeof(Node) ); temp-elem=ch; temp-next=NULL; current-next=temp; /* 当前节点的后驱指向新节点*/ current=temp; /* 当前节点为链表尾节点*/ current-next=head; /* 尾节点指向头节点*/return head; /*=*/* 判断链表是否有环( 循环链表 )*/bool IsCycleList(Node *head) if (NULL= head) returnfalse; if (NULL = head-next) returnfalse; Node *current=head-next; while(current) if (head = current-next) returntrue; current=current-next; returnfalse; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - int main() Node * head,*p; Node * head2,*head3; DNode * dHead; char ch; head = NULL; head2=NULL; head3=NULL; dHead=NULL; /head=(Node*) malloc ( sizeof( Node) ); /head-next = NULL; /创建单链表 head=CreateList(head); PrintList(head); head2=CreateList(head2); PrintList(head2); / 插入节点 coutch; InsertNode(head,ch); PrintList(head); / 删除节点 coutch; DeleteNode(head,ch); PrintList(head); / 单链表逆置 head=ReverseList(head); coutn Reversed !; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - PrintList(head); / 求中间节点 p=MiddleNode(head); coutn Middle Node is:; coutelemendl; / 合并有序单链表 MergeList(head,head2); coutn Merged!; PrintList(head); / 创建双链表 dHead=DoubleList(dHead); PrintDoubleList(dHead); /* 创建循环链表并判断是否有环*/ head3=CycleList(head3); coutIsCycleList(head3); return0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -