在双向链表存储结构中
① 单双向链表原理
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
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