#include <iostream,h>
#include <string.h>
struct Node
{
int num ;
Node *next ;
};
Node* Create() //链表创建
{
int n=0;
Node *p1,*p2,*head;
p1=p2=new Node;
cin>>p1->num;
head=NULL;
while (p1->num!=0)
{
if (n==1)
{
head=p1;
}
else
p2->next=p1;
p2=p1;
p1=new Node;
cin>>p1->num;
n++;
}
p2->next=NULL;
return head;
}
int ListLength(Node L) //链表的计数
{
Node p=L;
int count=0;
while(p->next)
{
count++;
p=p->next;
}
return count;
}
int Search(Node &L , int value) //链表的查找
{
Node p=L;
int index=0;
while(p)
{
if(p->num== value)
return index;
p=p->next;
index++;
}
return 0;
}
void Print(Node *head) //输出链表
{
Node* p=head;
while (p)
{
cout<<p->num<<" ";
p=p->next;
}
cout<<endl;
}
void Destruct(Node *head) //清空链表
{
Node *current = head, *temp = NULL;
while (current)
{
temp = current;
current = current ->next;
delete temp;
}
}
Node *ReverseList(Node *head) //链表逆序（循环方法）
{
Node *p,*q,*r;
p=head; //一开始 p指向第一个节点
q=p->next; //q 指向第二个节点
while (q!=NULL) //如果没到链尾
{ //以第一次循环为例
r=q->next; //r 暂时存储第三个节点
q->next=p; //没执行此句前，q->next指向第三个节点
//执行之后，q->next 指向第一个节点 p
p=q; //之后 p 指向第二个节点
q=r; //q指向第三个节点
//即...p=>q=>r...变为 ...p<=q<=r...
}
head->next=NULL; //最后原来的链头变为链尾，把它指向 NULL。
head=p; //原来的链尾变成链头
return head;
}
Node *ReverseList2(Node *head) //链表逆序（递归方法）
{
if (!head)
{
return NULL;
}
Node *temp = ReverseList2 (head->next);
if (!temp)
{
return head;
}
head->next->next = head;
head->next = NULL;
return temp;
}
递归时,head可以分别用 head ，head1,head2 ...headn-1, headn 来表示总共 n+1 个节点 temp = ReverseList2( head->next ); 此句的递归一直将参数传进来的。
Node* head 递归到 headn 然后判断下列语句：
else if( !headn->next )
{
return headn;
}
将返回值传给 temp,此时 temp 指向链尾 ,由于在此次返回,故此次没有执行最后的 else 的那部分的语
句,返回上一级即是 headn-1 那一级,继续执行
下面的 headn-1->next->next = headn-1;
headn-1->next = NULL; //此两句将最后两个逆序连接,
return temp;
//之后返回 temp 比上一层的 temp 即是执行 temp = ReverseList2( head->next )赋值,因为
递归的口都是在这里的,如果说好理解点也可以将 temp来编号
同理
在返回 temp 后,继续执行
headn-2->next->next = headn-2;
headn-2->next = NULL;
return temp;
.....
一直到 head时 即是原链表的第一个节点,在对其 head->next = NULL后,此时以 temp 所指向的节点为链头的逆序链表就形成了.
//已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。（循环方法）
//(保留所有结点，即便大小相同）
Node *Merge(Node *head1 , Node *head2)
{
if ( head1 == NULL)
return head2 ;
if ( head2 == NULL)
return head1 ;
if ( head1->num < =head2->num )
{
head = head1 ;
head1= head1->next;
}
else
{
head = head2 ;
head2 = head2->next ;
}
Node *temp = head ;
while ( head1 != NULL && head2 != NULL)
{
if ( head1->num <= head2->num )
{
temp->next = head1 ;
head1 = head1->next ;
temp =temp->next;
}
else
{
temp->next = head2;
head2 = head2->next ;
temp =temp->next;
}
}
if (head1 == NULL) temp->next = head2;
if (head2 == NULL) temp->next = head1;
return head;
}
//已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。（递归方法）
Node *MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->num < head2->num )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}
从递归函数的定义不难看出，这个函数定义中递归调用时形参发生改变，即是当前节点的下一个节点，每
一次递归都按照这个规律逐次遍历两个有序链表的每一个节点， 判断大小后使 head指向数据域较小的节
点，由堆栈空间的思想可知递归到最后指向 NULL 时才返回两个链表的某一个头节点，而此时
head->next=head2，head=head1链表的最后一个节点，该语句就使得这样一个指向关系确立起
来。
以上均通过理想的有序链表，即链表 1的任何一个数据值都小于链表 2来做分析，其他的情况讨论方式类
似。
Node* Delete(Node* head , int num) //删除节点
{
if (head==NULL)
{
cout<<"List is Null"<<endl;
return head;
}
Node *p1,*p2;
p1=head;
while (p1->num!=num && p1->next)
{
p2=p1;
p1=p1->next;
}
if (p1->num==num)
{
if (p1==head)
{
head=p1->next;
}
else
p2->next=p1->next;
}
else
cout<<"Do not Find The Num "<<num<<endl;
return head;
}
Node* Insert(Node* head , int num) //插入节点
{
Node *p0,*p1,*p2;
p1=head;
p0=new Node;
p0->num=num;
if (head==NULL)
{
head=p0;
p0->next=NULL;
return head;
}
while (p1->num<p0->num && p1->next)
{
p2=p1;
p1=p1->next;
}
if (p1->num>=p0->num)
{
if (p1==head)
head=p0;
else
p2->next=p0;
p0->next=p1;
}
else
{
p1->next=p0;
p0->next=NULL;
}
return head;
}
void main()
{省略不写}
双向链表
原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后，
这部分应该难不倒你。现在我的问题是，能不能从单链表派生出双向链表？
你可以有几种做法：
一种就是先定义一个双链节点--但是，它的名字必须叫 Node，这是没办法的事；不然
你就只好拷贝一份单链表的实现文件，把其中的 Node 全都替换成你的双链节点名字，但是
这就不叫继承了。
另一种做法就是先定义一种结构例如这样的：
template ＜class Type＞ class newtype
{
public:
Type data;
Node＜newtype＞ *link;
}
当你派生双向链表时，这样写 template ＜calss Type＞ class DblList : public List＜
newtype＜Type＞ ＞，注意连续的两个"＞"之间要有空格。或者根本不定义这样的结构，
直接拿 Node 类型来做，例如我下面给出的。但是，请注意要完成"=="的重载，否则，你又
要重写 Find 函数，并且其他的某些操作也不方便。
在开始完成你的从单链表派生出来的双向链表之前，要在单链表这个基类中添加修改当
前指针和当前前驱指针的接口，如下所示：
protected:
void Put(Node＜Type＞ *p)//尽量不用，双向链表将使用这个完成向前移动
{
current = p;
}
void PutPrior(Node＜Type＞ *p)//尽量不用，原因同上
{
prior = p;
}
因为这个接口很危险，而且几乎用不到，所以我在前面并没有给出，但要完成双向链表
最"杰出"的优点--向前移动当前指针，必须要使用。另外说的是，我从前也从来没计划从单
链表派生双链表，下面你将看到，这个过程很让人烦人，甚至不如重写一个来的省事，执行
效率也不是很好，这种费力不讨好的事做它有什么意思呢？的确，我也觉得我在钻牛角尖。
定义和实现
#ifndef DblList_H
#define DblList_H
#include "List.h"
template ＜class Type＞ class DblList : public List＜ Node＜Type＞ ＞
{
public:
Type *Get()
{
if (pGet() != NULL) return &pGet()-＞data.data;
else return NULL;
}
Type *Next()
{
pNext();
return Get();
}
Type *Prior()
{
if (pGetPrior != NULL)
{
Put(pGetPrior());
PutPrior( (Node＜ Node＜Type＞ ＞*)pGet()-＞data.link);
return Get();
}
return NULL;
}
void Insert(const Type &value)
{
Node＜Type＞ newdata(value, (Node＜Type＞*)pGet());
List＜ Node＜Type＞ ＞::Insert(newdata); if (pGetNext()-＞link != NULL)
pGetNext()-＞link-＞data.link = (Node＜Type＞*)pGetNext();
}
BOOL Remove()
{
if (List＜ Node＜Type＞ ＞::Remove())
{
pGet()-＞data.link = (Node＜Type＞*)pGetPrior();
return TURE;
}
return FALSE;
}
};
#endif
【说明】只完成了最重要的Insert和Remove函数和最具特点的Prior()函数，其他的没有
重新实现。所以，你在这里使用单链表的其他方法，我不保证一定正确。并且，这里的指针
类型转换依赖于编译器实现，我也不能肯定其他的编译器编译出来也能正确。对于让不让
Prior返回头节点的data，我考虑再三，反正用First();Get();这样的组合也能返回，所以就不
在乎他了，所以要是用Prior遍历直到返回NULL，就会将头节点的data输出来了。
【补充】至于双向循环链表，也可以从这个双向链表派生（仿照派生循环链表的方法）；
或者从循环链表派生（仿照派生双向链表的方法），就不一一举例了（再这样下去，我就真
闹心的要吐血了）。至此，可以得出一个结论，链表的各种结构都是能从单链表派生出来的。
换句话说，单链表是根本所在，如果研究透了单链表，各种链式结构都不难。
一小段测试程序
void DblListTest_int()
{
DblList＜int＞ a;
for (int i = 10; i ＞ 1; i--) a.Insert(i);
for (i = 10; i ＞ 1; i--) cout ＜＜ *a.Next() ＜＜ " ";
a.First();
cout ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl; a.Remove();
cout ＜＜ *a.Get() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
}
【后记】从我对双向链表不负责任的实现来看，我并不想这么来实现双向链表，我只是
尝试怎样最大限度的利用已有的类来实现这种类型。实践证明，不如重写一个。别人看起来
也好看一些，自己写起来也不用这样闹心。不过，这个过程让我对函数的调用和返回的理解
又更深了一步。如果你能第一次就写对这里的 Insert 函数，相信你一定对 C++有一定的感
触了。我也觉得，只有做一些创新，才能最已经很成熟的东西更深入的了解。比如，这些数
据结构，在 C++的标准库（STL）中都可以直接拿来用，我们为什么还辛辛苦苦的写，结果
还不如人家原来的好。为了学习，这就是理由，这也是一切看起来很笨的事发生的理由。
用链表的方法实现一个简单的电话本：
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<iomanip>
#include<string>
using namespace std;
//电话本单个成员
class Person
{
private:
string name;//姓名
string tel_num;//电话
public:
Person *next_ptr;//指向下一个成员的链结
Person(const string &n=0, const string &t=0);//构造
Person(Person &p); //拷贝构造函数
int FindName(const string &str); //找到该成员 是返回 1,否则返回 0
string& GetTel() {return tel_num;}; //得到电话号码
string& GetName() {return name;};//得到名字
};
//构造函数
Person::Person(const string &n, const string &t)
{
name = n;
tel_num = t;
next_ptr = NULL;
}
//拷贝构造函数
Person::Person(Person &p)
{
name = p.name;
tel_num = p.tel_num;
next_ptr = p.next_ptr;
}
//找到该成员
int Person::FindName(const string &str)
{
if (str == name)
{
return 1;
}
else
{
return 0;
}
}
//电话本
class PhoneBook
{
private:
Person * head_ptr;
public:
PhoneBook();//构造
void Create(Person newperson);//添加记录
void Delete(const string &deletename);//删除记录
void DeleteAll(); //删除所有记录
void Find(const string &fname);//查找记录
void Save();//保存到文件
void Load();//从文件读取 void PrintAll();//全部打印
~PhoneBook();//析构
};
//构造函数
PhoneBook::PhoneBook()
{
head_ptr = NULL;
}
//创建新记录
void PhoneBook::Create(Person newperson)
{
if (head_ptr == NULL)//若为空链表直接添加记录
{
head_ptr = new Person (newperson);
}
else
{
Person *p = head_ptr;
while (p -> next_ptr != NULL)//找到尾节点 为 p
{
p = p -> next_ptr;
}
p -> next_ptr = new Person (newperson);//添加记录
}
cout << "已添加新纪录" << endl;
}
//删除记录
void PhoneBook::Delete(const string &deletename)
{
if (head_ptr == NULL)//头为空
{
cerr << "还没有任何记录!" << endl;
system("pause");
}
else if (head_ptr -> next_ptr == NULL) //只有头
{
if(head_ptr -> FindName (deletename))
{ delete head_ptr;
head_ptr = NULL;
cout << "已成功删除" << deletename << endl;
}
else
{
cerr << "未找到这条记录!" << endl;
system("pause");
}
}
else //其他情况
{
Person *last = head_ptr;//记录上一个链节
Person *p = last -> next_ptr;
if(last -> FindName (deletename)) //删头
{
delete last;
head_ptr = p;
cout << "已成功删除" << deletename << endl;
}
else//其他情况
{
while (p != NULL && !(p -> FindName (deletename)))//遍历
{
last = last -> next_ptr;
p = last -> next_ptr;
}
if (p != NULL) //找到了
{
last -> next_ptr = p -> next_ptr;
delete p;
cout << "已成功删除" << deletename << endl;
}
else //没找到
{
cerr << "未找到这条记录!" << endl;
system("pause");
} }
}
}
//删除所有记录
void PhoneBook::DeleteAll()
{
if (head_ptr == NULL)//头为空
{
cerr << "还没有任何记录!" << endl;
system("pause");
}
else
{
Person *temp = head_ptr;
while (head_ptr != NULL)
{
head_ptr = head_ptr -> next_ptr;
delete temp;
temp = head_ptr;
}
head_ptr=NULL;
cout << "已删除所有联系人!" << endl;
}
}
//查找记录
void PhoneBook::Find (const string &fname)
{
if (head_ptr == NULL)//头为空
{
cerr << "还没有任何记录!" << endl;
system("pause");
}
else//有记录
{
Person *p = head_ptr;
while (p != NULL && !(p -> FindName (fname)))//遍历
{
p = p -> next_ptr; }
if (p != NULL) //找到了
{
cout << fname << "的电话号码是:" << p -> GetTel() << endl;
system("pause");
}
else //没找到
{
cerr << "未找到这条记录!" << endl;
system("pause");
}
}
}
//保存到文件
void PhoneBook::Save()
{
if (head_ptr == NULL)//头为空
{
cerr << "还没有任何记录!" << endl;
system("pause");
}
else//有记录
{
ofstream ofile("PhoneBook.txt",ios::out|ios::trunc);//打开文件
if (!ofile)
{
cerr << "无法打开 PhoneBook.txt" << endl;
system("pause");
}
else//成功打开
{
ofile.seekp(0,ios::beg);//重定位
Person *p = head_ptr;
int i=1;
ofile << "电话本:";
while (p != NULL)//遍历 {
ofile << '/n' << i << '.'
<< p -> GetName() << '/n'
<< "电话:" << setw(15) << p -> GetTel();
p = p -> next_ptr;
i++;
}
ofile.close();//关闭文件
cout << "成功保存到文件,请查看 PhoneBook.txt" << endl;
}
}
//从文件中读取
void PhoneBook::Load()
{
string filename;
cout << "请输入文件名(XXXXX.XXX):" << endl;
cin >> filename;
ifstream ifile(filename.c_str(), ios::in);//打开文件
if (!ifile)
{
cerr << "无法打开" << filename << endl;
system("pause");
}
else//成功打开
{
ifile.seekg(0,ios::beg);//重定位
int z;
string str;
getline(ifile,str);//欢迎信息
while(!ifile.eof())
{
ifile >> z;//数字
ifile.get();//点
string name;
string tel;
getline(ifile,name);//名字
ifile >> tel >> tel;//电话 Person per(name,tel);
Create (per);
}
Delete("");
ifile.close();
cout << "成功从文件" << filename << "中读取记录!" << endl;
}
}
//全部打印
void PhoneBook::PrintAll()
{
if (head_ptr == NULL)//头为空
{
cerr << "还没有任何记录!" << endl;
system("pause");
}
else//有记录
{
Person *p = head_ptr;
int i=1;
while (p != NULL)//遍历
{
cout << left << setw (4) << i << setw(20)
<< p -> GetName() << setw(15) << p -> GetTel() << endl;
p = p -> next_ptr;
i++;
}
system("pause");
}
}
//析构
PhoneBook::~PhoneBook()
{
Person *temp = head_ptr;
while (head_ptr != NULL)
{ head_ptr = head_ptr -> next_ptr;
delete temp;
temp = head_ptr;
}
cout << "已删除所有联系人!" << endl;
}
//功能选择
int Choice (void)
{
int ch;
cout << "/t/t/t请选择:/n"
<< "/t/t/t1.添加新的联系人/n"
<< "/t/t/t2.删除某个联系人/n"
<< "/t/t/t3.删除所有联系人/n"
<< "/t/t/t4.查询某个联系人/n"
<< "/t/t/t5.查询所有联系人/n"
<< "/t/t/t6.将电话本导出到文件/n"
<< "/t/t/t7.从文件导入电话本/n"
<< "/t/t/t0.退出系统" << endl;
cin >> ch;
return ch;
}
//主函数
main()
{
cout << "/t/t/t欢迎您使用电话本系统!/n/n" << endl;
PhoneBook mypb;
int ch;
while (ch=Choice())
{
switch(ch)
{
case 1://新增联系人
{
string name;
string tel;
cout << "请输入联系人姓名:" << endl;
cin.get();
getline (cin,name); cout << "请输入联系人电话:" << endl;
cin >> tel;
Person per(name,tel);
mypb.Create(per);
break;
}
case 2://删除联系人
{
string deletename;
cout << "请输入要删除的联系人姓名:"
<< endl;
cin.get();
getline (cin,deletename);
mypb.Delete(deletename);
break;
}
case 3://删除所有联系人
{
mypb.DeleteAll();
break;
}
case 4://查询某个联系人
{
string fname;
cout << "请输入要查询的联系人姓名:"
<< endl;
cin.get();
getline (cin,fname);
mypb.Find(fname);
break;
}
case 5:// 查询所有联系人
{
mypb.PrintAll();
break;
}
case 6://将电话本导出到文件
{
mypb.Save();
break;
} case 7:// 从文件导入电话本
{
mypb.Load();
break;
}
default:
{
cerr << "输入错误,请重新输入!" << endl;
break;
}
}
}
cout << "感谢您使用电话本系统,再见!" << endl;
system("pause");
return 0;
}
链表的 C 语言实现之循环链表及双向链表
一、循环链表
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个
结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单
链表那样置为 NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判定是否到表尾时，是判定该结点链域的值是否是表头结点，当链域值等于表头
指针时，说明已到表尾。而非象单链表那样判定链域值是否为 NULL。
二、双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表
头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后
继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接
前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一
般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在 c 语言中双向链表结
点类型可以定义为：
typedef strUCt node
{
int data; /*数据域*/
struct node *llink,*rlink; /*链域，*llink 是左链域指针，*rlink是右链域指针*/
}JD;
当然，也可以把一个双向链表构建成一个双向循环链表。
双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。
双向链表的基本运算：
1、查找
假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们
同样从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，
否则继续往后查，直到表尾。
下例就是应用双向循环链表查找算法的一个程序。
#include ＜stdio.h＞
#include ＜malloc.h＞
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i; if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h-＞name[0]=’’;
h-＞llink=NULL;
h-＞rlink=NULL;
p=h;
for(i=0;i＜n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
p-＞rlink=s;
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s-＞name);
s-＞llink=p;
s-＞rlink=NULL;
p=s;
}
h-＞llink=s;
p-＞rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h-＞rlink;
while(p!=h)
{
y=p-＞name;
if(strcmp(y,x)==0)
return(p);
else p=p-＞rlink;
}
printf("没有查找到该数据!");
}
void print(stud *h) {
int n;
stud *p;
p=h-＞rlink;
printf("数据信息为： ");
while(p!=h)
{
printf("%s ",&*(p-＞name));
p=p-＞rlink;
}
printf(" ");
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("请输入你要查找的人的姓名:");
scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s",*&searchpoint-＞name);
2、插入
对于双向循环链表，我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。
假若 s,p,q 是连续三个结点的指针，若我们要在 p 前插入一个新结点 r，则只需把 s 的右
链域指针指向 r，r 的左链域指针指向 s，r的右链域指针指向 p，p 的左链域指针指向 r 即可。
在 p,q 之间插入原理也一样。
下面就是一个应用双向循环链表插入算法的例子：
#include ＜stdio.h＞
#include ＜malloc.h＞
#include ＜string.h＞
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h-＞name[0]=’’;
h-＞llink=NULL;
h-＞rlink=NULL;
p=h;
for(i=0;i＜n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
p-＞rlink=s;
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s-＞name);
s-＞llink=p;
s-＞rlink=NULL;
p=s;
}
h-＞llink=s;
p-＞rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h-＞rlink; while(p!=h)
{
y=p-＞name;
if(strcmp(y,x)==0)
return(p);
else p=p-＞rlink;
}
printf("没有查找到该数据!");
}
void print(stud *h)
{
int n;
stud *p;
p=h-＞rlink;
printf("数据信息为： ");
while(p!=h)
{
printf("%s ",&*(p-＞name));
p=p-＞rlink;
}
printf(" ");
}
void insert(stud *p)
{
char stuname[20];
stud *s;
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
printf("请输入你要插入的人的姓名:");
scanf("%s",stuname);
strcpy(s-＞name,stuname);
s-＞rlink=p-＞rlink;
p-＞rlink=s;
s-＞llink=p;
(s-＞rlink)-＞llink=s;
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("请输入你要查找的人的姓名:");
scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s ",*&searchpoint-＞name);
insert(searchpoint);
print(head);
} //更多内容请看 C/C++进阶技术文档专题，或
3、删除
删除某个结点，其实就是插入某个结点的逆操作。还是对于双向循环链表，要在连续的
三个结点 s,p,q 中删除 p 结点，只需把 s 的右链域指针指向 q，q 的左链域指针指向 s，并收
回 p 结点就完成了。
下面就是一个应用双向循环链表删除算法的例子：
#include
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h-＞name[0]=’’; h-＞llink=NULL;
h-＞rlink=NULL;
p=h;
for(i=0;i〈n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
p-〉rlink=s;
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s-＞name);
s-＞llink=p;
s-＞rlink=NULL;
p=s;
}
h-＞llink=s;
p-＞rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h-＞rlink;
while(p!=h)
{
y=p-＞name;
if(strcmp(y,x)==0)
return(p);
else p=p-＞rlink;
}
printf("没有查找到该数据!");
}
void print(stud *h)
{
int n;
stud *p;
p=h-＞rlink;
printf("数据信息为： "); while(p!=h)
{
printf("%s ",&*(p-＞name));
p=p-＞rlink;
}
printf(" ");
}
void del(stud *p)
{
(p-＞rlink)-＞llink=p-＞llink;
(p-＞llink)-＞rlink=p-＞rlink;
free (p);
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("请输入你要查找的人的姓名:");
scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s ",*&searchpoint-＞name);
del(searchpoint);
print(head);
}