天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

链表的操作实例

Posted on 2012-03-01 11:49 hoshelly 阅读(405) 评论(0)  编辑 收藏 引用 所属分类: DS && Algorithm
要求:从终端输入一组整数(大于10),以0作为结束标志,将这一组整数存放在一个链表中(结束标志0不包括在内),打印出该链表中的值。然后删除该链表的第5个元素,打印出删除后的结果。最后在内存中释放掉该链表。
源程序如下:

#include<stdio.h>
#include
<stdlib.h>
#include
<conio.h>
typedef 
int ElemType;
typedef 
struct node{
    ElemType data;
    
struct node *next;
}LNode,
*LinkList;

LinkList GreatLinkList(
int n){
    LinkList p,r,list
=NULL;
    ElemType e;
    
int i;
    
for(i=1;i<=n;i++)
    {
        scanf(
"%d",&e);
        p
=(LinkList)malloc(sizeof(LNode));
        p
->data=e;
        p
->next=NULL;
        
if(!list)
            list
=p; //如果list为空,则说明本次生成的结点为第一个结点,将p赋给list
        else
            r
->next=p;//否则将p赋给r->next,这里r永远指向原先链表的最后一个结点,也就是要插入结点的前一个结点
        r=p;
    }
    
return list;//返回链表头指针
}

void insertList(LinkList *list,LinkList q,ElemType e)
{
    LinkList p;
    p
=(LinkList)malloc(sizeof(LNode));
    p
->data=e;
    
if(!*list){ //当链表为空时,将p赋给list,p的next域的值置为空
        *list=p;
        p
->next=NULL;
    }
    
else
    {
        p
->next=q->next;//q为插入指针指向的结点
        q->next=p;
    }
}

void delLink(LinkList *list,LinkList q){
    LinkList r;
    
if(q==*list)//如果删除第一个结点
    {
        
*list=q->next;
        free(q);
    }
    
else //删除其他结点
    {
        
for(r=*list;r->next!=q;r=r->next);//当q所指向的结点的前驱结点的指针未知时,需要先通过链表头指针list遍历链表,
                                           
//找到q的前驱结点的指针,并把该指针赋值给指针变量r
        if(r->next!=NULL){
            r
->next=q->next;
            free(q);
        }
    }
}

void destroyLinkList(LinkList *list){
    LinkList p,q;
    p
=*list;
    
while(p)//循环释放掉每个链表结点
    {
        q
=p->next;
        free(p);
        p
=q;
    }
    
*list=NULL;//将该链表完全置空,防止list变成野指针
}

void main()
{
    
int e,i;
    LinkList l,q;
    q
=l=GreatLinkList(1);//创建链表一个结点,q和l指向该结点
    scanf("%d",&e);
    
while(e) //循环输入数据,同时插入新生成的结点
    {
        insertList(
&l,q,e);
        q
=q->next;
        scanf(
"%d",&e);
    }
    q
=l;
    printf(
"The content of the linklist\n");
    
while(q) //输出链表中的内容
    {
        printf(
"%d ",q->data);
        q
=q->next;
    }
    q
=l;
    printf(
"\nDelete teh fifthe element\n");
    
for(i=0;i<4;i++)
    {
        q
=q->next;
    }
//将指针q指向链表的第5个元素

    delLink(
&l,q);
    q
=l;
    
while(q)
    {
        printf(
"%d ",q->data);
        q
=q->next;
    }
    destroyLinkList(
&l);
    getche();
//输入后立即从控制台取字符,不以回车为结束(带回显)
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理