在雙向鏈表存儲結構中
① 單雙向鏈表原理
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。
1鏈表操作編輯
雙向鏈表
雙向鏈表
線性表的雙向鏈表存儲結構：
帶頭結點的雙向循環鏈表的基本操作：
銷毀雙向循環鏈表L：
重置鏈表為空表：
驗證是否為空表：
2元素操作編輯
計算表內元素個數
賦值：
查找元素：
查找元素前驅：
查找元素後繼：
查找元素地址：
元素的插入：
元素的刪除：
正序查找：
逆序查找：
3循環鏈表編輯
循環鏈表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鏈表中的任何一個結點出發都能找到任何其他結點。循環鏈表的操作和單鏈表的操作基本一致，差別僅僅在於演算法中的循環條件有所不同。
② 雙向鏈表
#include <stdio.h>
typedef struct Link/*雙向鏈表結構悉好空體*/
{
int data;
struct Link *lift;
struct Link *right;
}linkx,*linky;
linky Init();/*建立雙向襪信鏈表*/
void PrLink(linky p);/*輸出雙向鏈表*/
linky Sort(linky head);/睜瞎*對雙向鏈表排序*/
linky Swap(linky head,linky one,linky two);/*任意交換雙向鏈表兩個結點的地址*/
void main(void)
{
linky head;
head=Init();
head=Sort(head);
PrLink(head);
}
linky Init()/*建立鏈表*/
{
linky p,q,head;
int n=0;
head=p=q=(linky)malloc(sizeof(linkx));
clrscr();
printf("please input 10 num: ");
scanf("%d",&p->data);/*輸入數據*/
head->lift=NULL;
n++;
while(n!=10)/*一直輸入到規定的數字個數停止*/
{
q=p;
p=(linky)malloc(sizeof(linkx));
scanf("%d",&p->data);/*輸入數據*/
q->right=p;
p->lift=q;
n++;
}
p->right=NULL;
return(head);
}
linky Swap(linky head,linky one,linky two)/*任意交換兩個結點*/
{linky temp;
if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交換*/
{
if(one->right==two)/*只有兩個結點的情況下*/
{
two->right=one;
two->lift=NULL;
one->lift=two;
one->right=NULL;
head=two;
}
else/*有間隔的首尾交換*/
{
one->right->lift=two;
two->lift->right=one;
two->right=one->right;
one->lift=two->lift;
two->lift=one->right=NULL;
head=two;/*尾結點成為頭結點*/
}
}
else if(two->right==NULL)/*尾和任意一個交換*/
{
if(one->right==two)/*交換最後兩個結點*/
{
one->lift->right=two;
two->lift=one->lift;
two->right=one;
one->lift=two;
one->right=NULL;
}
else/*和前面其他結點交換*/
{
temp=two->lift;
temp->right=one;
one->lift->right=two;
one->right->lift=two;
two->lift=one->lift;
two->right=one->right;
one->lift=temp;
one->right=NULL;
}
}
else if(one->lift==NULL)/*頭和任意一個交換*/
{
if(one->right==two)/*交換頭兩個結點*/
{
two->right->lift=one;
one->right=two->right;
one->lift=two;
two->right=one;
two->lift=NULL;
head=two;
}
else/*頭結點和後面其他結點交換*/
{
temp=one->right;
temp->lift=two;
one->lift=two->lift;
one->right=two->right;
two->lift->right=one;
two->right->lift=one;
two->right=temp;
two->lift=NULL;
head=two;/*交換的結點成為頭結點*/
}
}
else/*當中的任意兩個交換*/
{
if(one->right==two)/*交換連在一起的兩個結點*/
{
temp=one->lift;
one->lift->right=two;
one->right->lift=two;
one->lift=two;
one->right=two->right;
two->right->lift=one;
two->right=one;
two->lift=temp;
}
else/*交換隔開的兩個結點*/
{
one->lift->right=two;
one->right->lift=two;
one->lift=two->lift;
temp=one->right;
one->right=two->right;
two->lift->right=one;
two->right->lift=one;
two->right=temp;
two->lift=one->lift;
}
}
return(head);
}
linky Sort(linky head)/*對鏈表排序*/
{
linky i,j,t,p;
int max;
p=head;
for(i=p;i->right!=NULL;i=i->right)/*用選擇法的思想對這些結點排序*/
{
max=i->data;
for(j=i->right;j!=NULL;j=j->right)
if(j->data<max)
{
max=j->data;
t=j;
}
if(max!=i->data)/*如果沒有找到比i小的結點*/
{
head=Swap(head,i,t);/*因為最終返回的是頭結點,而頭結點又有可能變化,所以每次頭結點返回*/
i=t;
}
}
return(head);
}
void PrLink(linky p)/*輸出鏈表*/
{
linky q;
printf("Now the link: ");
do
{
q=p;
printf("%d ",p->data);
p=p->right;
free(q);/*釋放輸出結點*/
}
while(p!=NULL);
getch();
}
③ 問題在補充說明中 請幫幫忙啊
void SelectNode(LinkList L)
{
if(L->prior == NULL)
{
return ;
}
if(L->prior->freq < L->freq)
{//與胡銷上個結點交換鉛備
L->prior = L->prior->prior ;
L->next->prior = L->褲激游prior->next ;
L->prior->next->next = L->next ;
L->prior->next ->prior = L ;
L->prior->next = L ;
L->next = L->next->prior ;
SelectNode(L) ;
}
}
void LocateNode( LinkList L, DataType x)
{
LinkList *p1 ;
if(L.data == x)
{
L->freq ++ ;
SelectNode(L) ;
}
else
{
if(L->next != NULL)
{
L = L->next ;
LocateNode(L , x) ;
}
else
{
p1=(struct LinkList *)malloc(sizeof(LinkList));
p1->freq = 0; //創建時不算在頻度中
p1->data = x ;
L->next = p1 ;
p1->prior = L ;
p1->next = NULL ;
}
④ 線性表的雙向循環鏈表存儲結構及其上的基本操作，至少要求實現10個以上的基本操作
/*
下面有結果
*/
# include <stdio.h>
# include <stdlib.h>
# define TRUE 1
# define FALSE 0
# define OK 1
# define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct DuLNode
{
ElemType data;
DuLNode * prior,* next;
}DuLNode,* DuLinkList;
Status equal(ElemType c1, ElemType c2)
{
if (c1 == c2)
{
return TRUE;
}
else
{
return FALSE;
}
}
int comp(ElemType a, ElemType b)
{
if (a == b)
{
return 0;
}
else
{
return (a-b)/abs(a-b);
}
}
void print(ElemType c)
{
printf("%d ",c);
}
void print2(ElemType c)
{
printf("%c ",c);
}
void print1(ElemType * c)
{
printf("%d ",* c);
}
//產生空的雙向循環鏈表L，
void InitList(DuLinkList * L)
{
* L = (DuLinkList)malloc(sizeof(DuLNode));
if (* L)
{
(* L)->next = (* L)->prior = * L;
}
else
{
exit(0);
}
}
//銷毀雙向循環鏈表L
void DestroyList(DuLinkList * L)
{
DuLinkList q,p = (* L)->next;
while (p != (* L))
{
q = p->next;
free(p);
p = q;
}
free(* L);
(* L) = NULL;
}
//將L重置為空表
void ClearList(DuLinkList L)
{
DuLinkList q,p = L->next;
while (p != L)
{
q = p->next;
free(p);
p = q;
}
L->next = L->prior = L;
}
//線性表L已經存衫慎在，如果L為空表，則返回TRUE，否則返正困回FALSE
Status ListEmpty(DuLinkList L)
{
if (L->next==L && L->prior==L)
{
return TRUE;
}
else
{
return FALSE;
}
}
//L已經存在，返回L中數據或清敬元素的個數
int ListLength(DuLinkList L)
{
int i = 0;
DuLinkList p = L->next;
while (p != L)
{
i++;
p = p->next;
}
return i;
}
//當第i個元素存在時，將其值賦給e，並返回OK，否則返回FALSE
Status GetElem(DuLinkList L,int i,ElemType * e)
{
int j = 1;
DuLinkList p = L->next;
while (p!=L && j<i)
{
p = p->next;
j++;
}
if (p==L || j>i)
{
return ERROR;
}
* e = p->data;
return OK;
}
//返回L中第一個與e滿足關系compare的數據元素的位序
//如果這樣的元素不存在，則返回值為0
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
int i = 0;
DuLinkList p = L->next;
while (p != L)
{
i++;
if (compare(p->data,e))
{
return i;
}
p = p->next;
}
return 0;
}
//如果cur_e是L的數據元素，並且不是第一個，則用pre_e返回它的前驅
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType * pre_e)
{
DuLinkList p = L->next->next;//p指向第二個元素
while (p != L)
{
if (p->data == cur_e)
{
* pre_e = p->prior->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
//如果cur_e是L的數據元素，並且不是最後一個，
//則用next_e返回它的後繼元素，否則操作失敗，next_e沒有定義
Status NextElem(DuLinkList L,ElemType cur_e,ElemType * next_e)
{
DuLinkList p = L->next->next;
while (p != L)
{
if (p->prior->data == cur_e)
{
* next_e = p->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
//返回雙向鏈表L的第i個元素的地址，如果i = 0，則返回頭結點的地址
//如果第i個元素不存在，則返回NULL
DuLinkList GetElemP(DuLinkList L,int i)
{
int j;
DuLinkList p = L;
if (i<0 || i>ListLength(L))
{
return NULL;
}
for (j=1; j<=i; ++j)
{
p = p->next;
}
return p;
}
//在帶頭結點的雙鏈循環線性表L中的第i個位置之前插入元素e，
Status ListInsert(DuLinkList L,int i,ElemType e)
{
DuLinkList p,s;
if (i<1 || i>ListLength(L)+1)
{
return ERROR;
}
p = GetElemP(L,i-1);
if (!p)
{
return ERROR;
}
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s)
{
return 0;
}
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
//在帶頭結點的雙鏈循環線性表L中，刪除其第i個元素，
Status ListDelete(DuLinkList L,int i,ElemType * e)
{
DuLinkList p;
if (i<1)
{
return ERROR;
}
p = GetElemP(L,i);
if (!p)
{
return ERROR;
}
* e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
//由雙鏈循環線性表L的頭結點出發，正序對每個元素調用函數visit
//主要是正序
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{
DuLinkList p = L->next;//p指向頭結點
while (p != L)
{
visit(p->data);
p = p->next;
}
printf("\n");
}
//從雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函數visit
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{
DuLinkList p = L->prior;
while (p != L)
{
visit(p->data);
p = p->prior;
}
printf("\n");
}
int main(void)
{
DuLinkList L;
int i,n;
Status j;
ElemType e;
InitList(&L);
for (i=1; i<=5; ++i)
{
ListInsert(L,i,i);
}
printf("正序輸出鏈表：");
ListTraverse(L,print);
printf("逆序輸出鏈表：");
ListTraverseBack(L,print);
n = 2;
ListDelete(L,n,&e);
printf("刪除第%d個結點，其值是%d,其餘的結點是(正序輸出)：\n",n,e);
ListTraverse(L,print);
printf("鏈表的元素個數為%d\n",ListLength(L));
printf("鏈表是否空：%d(1:空 0:非空)\n",ListEmpty(L));
ClearList(L);
printf("清空後，鏈表空嗎：%d(1:空 0:非空)\n",ListEmpty(L));
printf("重新插入5個元素：\n然後正序遍歷：");
for (i=1; i<=5; ++i)
{
ListInsert(L,i,i);
}
ListTraverse(L,print);//正序輸出
n = 3;
j = GetElem(L,n,&e);
if (j)
{
printf("鏈表的第%d個元素的值為%d\n",n,e);
}
else
{
printf("不存在第%d個元素\n",n);
}
n = 4;
i = LocateElem(L,n,equal);
if (i)
{
printf("L中第%d個元素是%d\n",i,n);
}
else
{
printf("L中沒有元素%d\n",n);
}
j = PriorElem(L,n,&e);
if (j)
{
printf("%d的前驅是%d\n",n,e);
}
else
{
printf("%d沒有前驅\n");
}
j = NextElem(L,n,&e);
if (j)
{
printf("%d的後繼是%d\n",n,e);
}
else
{
printf("%d沒有後繼元素\n");
}
DestroyList(&L);
return 0;
}
/*
在vc++6.0中的輸出結果：
------------------------
正序輸出鏈表：1 2 3 4 5
逆序輸出鏈表：5 4 3 2 1
刪除第2個結點，其值是2,其餘的結點是(正序輸出)：
1 3 4 5
鏈表的元素個數為4
鏈表是否空：0(1:空 0:非空)
清空後，鏈表空嗎：1(1:空 0:非空)
重新插入5個元素：
然後正序遍歷：1 2 3 4 5
鏈表的第3個元素的值為3
L中第4個元素是4
4的前驅是3
4的後繼是5
Press any key to continue
------------------------------
*/
⑤ 關於數據結構（C語言）的幾個題
1.
voidconverse(intn,intd){
SqStackS;//新旦頃搭建一個棧
InitStack(S);//初始化棧
intk,e;
while(n>0){
k=n%d;
push(S,k);
n=n/d;
}//將余數進棧
while(S.top!=S.base){
模拿pop(S,e);
printf("%1d",e);
}//輸出結果
}
8.
先序遍歷：ABCDEF
中序遍歷：BCDAFE
後序遍歷：DCBFEA
⑥ 4． 在雙向鏈表中，每個結點包含有兩個指針域，一個指向其_____ ______結點，另一個指向其_____ ____結點
在雙向鏈表中，每個結點包含有兩個指針域，一個指向其後繼結點，另一個指向握前其前驅結點。
當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接後繼結點地址的鏈域。
在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個段態清存儲直接後繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。
(6)在雙向鏈表存儲結構中擴展閱讀：
在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種情況還使用於在最後一個結點後插入一個新的結點。
在判斷是否到表尾時，是判斷該結點閉改鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。
⑦ 雙向循環鏈表的概念
本課主題： 循環鏈表與雙腔拿向鏈表
教學目的： 掌握循環鏈表的概念，掌握雙向鏈表的的表示與實現
教學重點： 雙向鏈表的表示與實現
教學難點： 雙向鏈表的存儲表示
授課內容：
一、復習線性鏈表的存儲結構
二、循環鏈表的存儲結構
循環鏈表是加一種形式的鏈式存儲結構。它的特點是表中最後一個結點的指針域指向頭結點。
循環鏈表的操作和線性鏈表基本一致，差別僅在於演算法中的循環條件不是p或p->next是否為空，而是它們是否等於頭指針。
三、雙向鏈表的存儲結構
提問：單向鏈表的缺點是什麼？
提示：如何尋找結點的直接前趨。
雙向鏈表可以拍圓慧克服單鏈表的單向性的缺點。
在雙向鏈表的結點中有兩個指針域，其一指向直接襲答後繼，另一指向直接前趨。
1、線性表的雙向鏈表存儲結構
typedef struct DulNode{
struct DulNode *prior;
ElemType data;
struct DulNode *next;
}DulNode,*DuLinkList;
對指向雙向鏈表任一結點的指針d，有下面的關系：
d->next->priou=d->priou->next=d
即：當前結點後繼的前趨是自身，當前結點前趨的後繼也是自身。
2、雙向鏈表的刪除操作
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
if(!(p=GetElemP_DuL(L,i)))
return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->pror;
free(p);
return OK;
}//ListDelete_DuL
3、雙向鏈表的插入操作
Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e){
if(!(p=GetElemP_DuL(L,i)))
return ERROR;
if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return OK;
}//ListInsert_DuL
⑧ .在雙向鏈表存儲結構中,刪除p所指的結點的前趨結點(若存在)時需修改指針 . A. ((p->llink) ->llink) ->rl
①p->llink->llink->rlink=p;
②p->link=p->llink->llink;
說明：
要想空察刪除結點p的前趨結點，就要找到結點p的前趨結點的前趨結點神虧燃q，這里為了方便游虛說明，我叫它為結點q；
p結點的前趨結點的前趨結點為：p->llink->llink，即q=p->llink->llink
①將q的後趨指向p
②將p的前趨指向q