【問題描述】試實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2,a3....an）逆置為（an...a3,a2,a1）.

? ?[分析]就地逆置就是不需要額外申請(qǐng)結(jié)點(diǎn)空間，只需要利用原來的表中的結(jié)點(diǎn)空間。若對(duì)順序表中的元素進(jìn)行逆置，可 ? 以借助“交換”前后相應(yīng)元素的方法實(shí)現(xiàn)，但是對(duì)于單鏈表就不能“交換”，時(shí)間復(fù)雜度就會(huì)達(dá)到O(n^2)。

? 【思想】逆置后的單鏈表初始化為空表，表中的結(jié)點(diǎn)不是新生成的，而是從原鏈表中依次“刪除”，再逐個(gè)以頭插法放置到逆置表中，如此循環(huán)，直至原鏈表為空表止。

#include <stdio.h> #include <stdlib.h> #define ElemType char typedef struct Node /*結(jié)點(diǎn)類型定義*/ { ElemType data;struct Node * next; }Node, *LinkList; /* LinkList為結(jié)構(gòu)指針類型*/LinkList CreateFromTail() /*通過鍵盤輸入表中元素值，利用尾插法建單鏈表,并返回該單鏈表頭指針L*/ { LinkList L;Node *r, *s;char c;int flag =1; /*設(shè)置一個(gè)標(biāo)志，初值為1，當(dāng)輸入"$"時(shí)，flag為0，建表結(jié)束*/L=(Node * )malloc(sizeof(Node)); L->next=NULL; /*為頭結(jié)點(diǎn)分配存儲(chǔ)空間，建立空的單鏈表L*/r=L; /*r指針動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn)*/while(flag) /*循環(huán)輸入表中元素值，將建立新結(jié)點(diǎn)s插入表尾*/{c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL; /*將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表的結(jié)束*/}} return L; } void ReverseList(LinkList L) { Node *p,*q;p=L->next;L->next=NULL;while(p!=NULL){ q=p->next; /*q指針保留p->next得值*/p->next=L->next;L->next=p; /*將p結(jié)點(diǎn)頭插入到單鏈表L中*/p=q; /*p指向下一個(gè)要插入的結(jié)點(diǎn)*/} }int main() {LinkList l;Node *p;printf("用尾插法建立單鏈表,請(qǐng)輸入鏈表數(shù)據(jù),以$結(jié)束!\n");l = CreateFromTail();printf("輸入的單鏈表為:\n");p = l->next;while(p!=NULL){printf("%c\n",p->data);p=p->next;}ReverseList(l);printf("逆置后的單鏈表為:\n");p = l->next;while(p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");return 0; }

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的单链表的应用 就地逆置的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。