&&&&&&&&&&&&&
单链表是线性表的一种链式存储，属于线性结构，是通过指针来实现链式存储的，比之以顺序表，其存储密度更低，但是在插入，
删除操作上，其效率比顺序表要高；
（一）单链表的结构
typedef struct Node {&&& DataT&&& struct Node * }LNode,*LinkL
（二）单链表上的基本运算实现
（1）建立不带头结点的单链表
（a）从头部插入（与读入数据顺序相反）
#define flag 0
LinkList Creat_LinkList()
LinkList L;&&&
LNode *s;&&&
L=NULL;&&&&&&
scanf("%d",&x);&&&
while(x!=flag)&&&
s=(LNode *)malloc(sizeof(LNode));&&&&&&&
s-&data=x;&&&&&&&
s-&next=L;&&&&&&&
L=s;&&&&&&&
scanf("%d",&x);&&&
（b）从尾部插入（与读入数据顺序相同）
#define flag 0
LinkList Creat_LinkList()
LinkList L;&&&
LNode *s,*r;&&&
L=r=NULL;&&&&&&
scanf("%d",&x);&&&
while(x!=flag)&&&
& s=(LNode *)malloc(sizeof(LNode));&&&&&&&
s-&data=x;&&&&&&&
if(L==NULL)&&&&&&&&&&&
L=s;&&&&&&&
else&&&&&&&&&&&
r-&next=s;&&&&&&&
r=s;&&&&&&&
scanf("%d",&x);&&&
if(r)&&&&&&
&& r-&next=NULL;&&&
（2）求表长
（a）带头结点
int Length_LinkList(LinkList L)
int i=0;&&&
LNode *p;&&&
while(p-&next)&&
&& p=p-&&&&&&&&&
（b）不带头结点
int Length_LinkList(LinkList L)
int i=0;&&&
LNode *p;&&&
while(p)&&&
& i++;&&&&&&&
& p=p-&&&&
#include&stdio.h&#include&string.h&#include&stdlib.h&typedef int DataT#define flag 0typedef struct Node {
struct Node *}LNode,*LinkL//定义单链表LNode *Creat_LinkList()//创建带头结点的单链表{
LinkList L;
LNode *s,*r;
s=(LNode *)malloc(sizeof(LNode));
s-&next=NULL;
scanf("%d",&x);
while(x!=flag)
s=(LNode *)malloc(sizeof(LNode));
s-&data=x;
if(L-&next==NULL)
L-&next=s;
r-&next=s;
scanf("%d",&x);
if(r!=NULL)
r-&next=NULL;
return L;}LinkList reverse(LinkList L)//单链表的倒置算法{
L-&next=NULL;
q-&next=L-&
L-&next=q;
return L;}int main(){
LinkList H;
H=Creat_LinkList();
printf(" %d",p-&data);
printf("\n");
LinkList S;
S=reverse(H);
printf(" %d",q-&data);
printf("\n");
system("pause");
return 0;}
阅读(...) 评论()数据结构第二章习题_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
数据结构第二章习题
上传于||暂无简介
大小：113.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢最新碎语：胡东东博客,记录日常开发的问题和学习中的点滴
您的位置： && 单向链表的操作
#include &iostream&
typedef char ElemT//定义char类型的ElemType，方便修改
typedef struct LNode//定义一个结构体
ElemT//链表数据区
LNode *//链表指针区
void initList(LinkList * & L)
L=(LinkList *)malloc(sizeof(LinkList));//为链表开辟空间
L-&next=NULL;//带头节点的顺序链表
void createList (LinkList * &L,ElemType a[],int n)//插入数据
LinkList *p;
for(i=0;i&n;i++)//头插法 ，输出结果是逆序的
p=(LinkList *)malloc(sizeof(LinkList));
p-&data=a[i];
p-&next=L-&
p-&next=p;
int locateElem(LinkList *L,ElemType e)//查找元素
LinkList *p=L-&//第一个元素
while (p&&p-&data!=e)//判断链表是否为空，然后查找链表里的元素
if(!p)//查找完了，没找到
cout&&"没有这个元素!"&&
void listInsert(LinkList * &L,int i,ElemType e)//插入一个元素
//[i&=1&&i&=size+1]
cout&&"无法插入!"&&
//1.检查i&＝size＋1
2.找到插入位置
LinkList *p=L,*q;
while (p&&j&i-1)//p不存在退出，j&=i-1退出
cout&&"无法插入!"&&
q=(LinkList *)malloc(sizeof(LinkList));//开辟一个q链表
q-&data=e;
q-&next=p-&
//插入节点 （p插入位置前面一个元素，q需要插入的元素）
p-&next=q;
cout&&"插入完成!"&&
void nixuList(LinkList *&L)//逆序
LinkList *p,*t,*q;
if(L==NULL||L-&next==NULL)
cout&&"无法逆序输出!"&&
p-&next=NULL;
while(t)//
t-&next=L-&
L-&next=t;
listDelete(LinkList * &L,int i)//删除一个元素（位置）
cout&&"无法删除!"&&
//1.检查i&＝size＋1
2.找到插入位置
LinkList *p=L,*q;
while (p&&j&i-1)//p不存在退出，j&=i-1退出
cout&&"无法删除!"&&
//p要删除的元素的前一个
q=p-&//要删除的对象
if(q==NULL)
cout&&"无法删除!"&&
p-&next=q-&
cout&&"删除成功!"&&
void dispList(LinkList*L)
if(L==NULL||L-&next==NULL)
cout&&"链表为空！"&&
LinkList *p=L-&
printf("%c ",p-&data);
putchar('\n');
void destroyList (LinkList *&L)//销毁链表
LinkList *p=L-&//指向第一个元素
while (L-&next)
L-&next=p-&
free(p);//释放原来第一个元素
p=L-&//p指向第一个元素
//free(p);//要不要？
free(L);//释放head
L-&next=NULL;
cout&&"销毁完成!"&&
int main(int argc, const char * argv[])
LinkList *p =
*******************\n");
1.创建单链表
2.查找单链表元素
3.插入元素
4.删除元素
5.输出链表元素
6.销毁单链表
7.逆序输出
*******************\n");
printf("选择(1-8):");
scanf("%d",&n);
ElemType elem_create,elem[50];
printf("请输入元素(头插)(字符之间无空格):\n");
getchar();
while((elem_create=getchar())!='\n')
elem[j++]=elem_
initList(p);
createList(p,elem,j);
printf("链表创建完成!\n\n");
ElemType elem_
printf("请输入要查找的元素:");
getchar();
elem_search=getchar();
if(locateElem(p,elem_search))
if(locateElem(p,elem_search))
printf("要查找的元素是第%d个数据结点
\n",locateElem(p,elem_search));
printf("找不到元素%c\n\n",elem_search);
ElemType elem_
printf("输入插入位置和元素(逗号隔开):");
scanf("%d,%c",&loc_insert,&elem_insert);
listInsert(p,loc_insert,elem_insert);
printf("输入删除位置:");
scanf("%d",&loc_del);
listDelete(p,loc_del);
printf("链表元素有:\n");
dispList(p);
putchar('\n');
destroyList(p);
printf("逆序输出!\n");
nixuList(p);
printf("请输入正确的数字!\n\n");
本文由整理,转载请注明本文标题和链接本文标题: 《》本文链接:小木虫 --- 500万硕博科研人员喜爱的学术科研平台
程序员考试补课笔记-第十六天作者: 收集于网络
今天继续是链表方式的排序，前天的一题大家有没有弄懂了。弄不懂不要紧，这是要慢慢来的，急不来。&
p=h-&h-&next=NULL;&
　　while(p)&
　　　　if(p-&data&h-&data)&
　　　　{&
　　　　　　q=p-&&
　　　　　　p-&next=h;&
　　　　　　h=p;p=q;&
　　　　}&
　　　　else&
　　　　{&
　　　　　　q=h;r=q-&&
　　　　　　while(r&&&&p-&data&&&r-&data)&
　　　　　　{&
　　　　　　　　q=r;r=r-&&
　　　　　　}&
　　　　　　q-&next=p;p=p-&&
　　　　　　q-&next-&next=r;&
　　　　}&
　　按照这条程序的思路让我们来想想整个的过程，这个程序分了两部份，一部分就是如果当前待排序的结点值是小于头的结点值就直接把它插到第一个里，因为如果对比头的那个已经小于它了，所以后面的都不要比较了。如果待插入排序的结点值不是小于当前头结点的话，那么就应该要找到合适的位置才可以插入该结点了，我们来看q和r指针是用来做什么来的，它指向头指针h和r指向q指针的一下个结点，因为我们知道单向链表的缺点是不能知道它前面的结点是什么，所以一断开就可能会导至链表失败。我们的目的就是用q来保存它的前一个结点。在while循环里就是有两种可能，一种是r为空，这里r为空时就是说明了这个链表已经比到最后一个了，所以直接把待插入的结点插在后面就行了。至于p-&data&r-&data是要等p-&data比r-&data小时就说明已经找到该插入的位置里，我们就可以继续往下进行插入的步骤。while里面的是如果这两个条件都是真的时候说明还没有找到，那么就让两个双链指针往后移一个继续比较，等找到符合了就可以插入了。&
如果还是比较模糊的话大家不要紧，再看看下面这条程序：&
struct&node&*li_sort(struct&node&*h)&
　　struct&node&*t,*s,*u,*v;&
　　s=h-&&
　　h-&next=NULL;&
　　while(s!=NULL)&
　　　　for(t=s,v=h;v!=NULL&&&&v-&data&&&t-&&u=v,v=v-&next);&
　　　　　　s=s-&&
　　　　if(v==h)&h=t;&
　　　　else&u-&next=t;&
　　　　t-&next=v;&
　　我们可以看出这个程序很像上面的，但它更简化了，把整个判断都在一个for语句里了。我们慢慢来分析一下这个程序，相信只有去想的话大家应该都会明白的了。S=h-&next&和h-&next=NULL这两句都是同上一样，把他们分开成已排序部份和待排序部份。跟着主要的是要看看for语句里的，因为所有判断条件都在这里了。这里t是临时变量代s的，s的角色就是当前要插入的那个结点，v和u指针都和上面一程序的q和r是一样的，都是用来补缺单向链表的缺点。这里的条件也是一样，和上面程序的分别就是它整合了两种情况的可能性在，跟着下面的程序又作了一个条件来分别这是插入头的还是中间的。好了，还是一句要自己的脑根去想，这里第十六天图一里有整个的过程。&
　　说完了单向链表的当然就是要讲讲双向链表了，因为双向链表可以往前移的关系，所以程序也比较好办，不过麻烦的就是它的插入和删除操作，也当再一次练习链表操作的机会吧。大家先自己想想，再试着写出程序来，有了上面单向链表的基础应该也很容易可以跟着思路编出。大家把编好的程序发到http://zhgpa.vicp.net/bbs&程序员考试那版里，看看大家的方法有何不同一齐讨论。大家先不要看我下面的程序：&
一些定义略&
　　for(q=p-&pre,r=p;q&&&&p-&data&&&q-&&q=q-&pre);&
　　p=p-&&
　　r-&pre-&next=p;&
　　if&(p)&p-&pre=r-&&
　　if(q)&
　　　　p-&next=q-&&
　　　　if(q-&next)&q-&next-&pre=p;&
　　　　p-&pre=q;&
　　　　q-&next=p;&
　　　　r-&next=h;&
　　　　r-&pre=NULL;&
　　　　h-&pre=r;&
　　好了，大家的程序又是如何呢？希望大家多多讨论。这几天虽然学的内容不算多，但是就从中吸受到很多经验，现在链表的操作又更一步的前进了。懂得了分析程序的一些方法，编程这条路看起来真的很漫长，我在这条路里我什么都不懂，可是我会坚持。&
本栏目更多导读： 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
第二章_线性表(参考答案)
下载积分：2000
内容提示：第二章_线性表(参考答案)
文档格式：DOC|
浏览次数：66|
上传日期： 11:00:33|
文档星级：
该用户还上传了这些文档
第二章_线性表(参考答案)
官方公共微信}