`
yangzhizhen
  • 浏览: 75615 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

数据结构之链表(C实现)

    博客分类:
  • C
阅读更多
  • 前言

最近在复习数据结构的相关知识,感觉在初学的时候还是有很多东西没有掌握,不过现在终于算是搞得比较有头绪了,所以就在写出来和大家一起分享!

  • 什么是链表

简单的说,链表就是由多个结点离散分配,彼此通过指针相连,每个结点只有一个前驱结点和后继结点。首节点无前驱结点,为结点无后继结点的一种存储结构。

  • 链表的结构

头结点:链表的第一个有效结点前面的结点,头结点并不存放有效数据,也就是数据域为空,加头结点的主要目的是为了方便链表的操作。

首节点:链表的第一个有效结点,结点包含数据域和指针域。

尾结点:尾结点的指针域为空。

头指针:指向头结点的指针变量,它存放了头结点的地址(在这里注意一下,指针变量存放的是地址,也就是说头指针存放的是头结点的地址,一般通过头指针对链表进行操作)。

  • 具体实现
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//定义链表节点
typedef struct Node
{
 int data;    //数据域
 struct Node * pNext; //指针域
}NODE, * PNODE;    //NODE等价于struct Node, PNODE等价于struct Node *

//函数声明
PNODE createLinkList(void);        //创建链表的函数
void traverseLinkList(PNODE pHead);      //遍历链表的函数
bool isEmpty(PNODE pHead);        //判断链表是否为空的函数
int getLength(PNODE pHead);        //获取链表长度的函数
bool insertElement(PNODE pHead, int pos, int val);  //向链表中插入元素的函数,三个参数依次为链表头结点、要插入元素的位置和要插入元素的值
bool deleteElement(PNODE pHead, int pos, int * pVal); //从链表中删除元素的函数,三个参数依次为链表头结点、要删除的元素的位置和删除的元素的值
void sort(PNODE pHead);         //对链表中的元素进行排序的函数(基于冒泡排序)
int main(void)
{
 int val;     //用于保存删除的元素
 PNODE pHead = NULL;   //PNODE等价于struct Node *
 pHead = createLinkList(); //创建一个非循环单链表,并将该链表的头结点地址赋给pHead
 traverseLinkList(pHead); //调用遍历链表的函数
 if(isEmpty(pHead))
  printf("链表为空!\n");
 else
  printf("链表不为空!\n");
 printf("链表的长度为:%d\n", getLength(pHead));
 //调用冒泡排序函数
 sort(pHead);
 //重新遍历
 traverseLinkList(pHead);
 //向链表中指定位置处插入一个元素
 if(insertElement(pHead, 4, 30))
  printf("插入成功!插入的元素为:%d\n", 30);
 else
  printf("插入失败!\n");
 //重新遍历链表
 traverseLinkList(pHead);
 //删除元素测试
 if(deleteElement(pHead, 3, &val))
  printf("元素删除成功!删除的元素是:%d\n", val);
 else
  printf("元素删除失败!\n");

 traverseLinkList(pHead);
 system("pause");
 return 0;
}

PNODE createLinkList(void)
{
 int length;  //有效结点的长度
 int i;
 int value;  //用来存放用户输入的结点的值
 //创建了一个不存放有效数据的头结点
 PNODE pHead = (PNODE)malloc(sizeof(NODE));
 if(NULL == pHead)
 {
  printf("内存分配失败,程序退出!\n");
  exit(-1);
 }
 PNODE pTail = pHead; //pTail始终指向尾结点
 pTail->pNext = NULL; //清空指针域
 printf("请输入您想要创建链表结点的个数:len = ");
 scanf("%d", &length);
 for(i=0;i<length;i++)
 {
  printf("请输入第%d个结点的值:", i+1);
  scanf("%d", &value);
  PNODE pNew = (PNODE)malloc(sizeof(NODE));
  if(NULL == pHead)
  {
   printf("内存分配失败,程序退出!\n");
   exit(-1);
  }
  pNew->data = value;  //向新结点中放入值
  pTail->pNext = pNew; //将尾结点指向新结点
  pNew->pNext = NULL;  //将新结点的指针域清空
  pTail = pNew;   //将新结点赋给pTail,使pTail始终指向为尾结点
 }
 return pHead;
}

void traverseLinkList(PNODE pHead)
{
 PNODE p = pHead->pNext;
 while(NULL != p)
 {
  printf("%d  ", p->data);
  p = p->pNext;
 }
 printf("\n");
 return;
}

bool isEmpty(PNODE pHead)
{
 if(NULL == pHead->pNext)
  return true;
 else
  return false;
}

int getLength(PNODE pHead)
{
 PNODE p = pHead->pNext;   //指向首节点
 int len = 0;     //记录链表长度的变量
 while(NULL != p)
 {
  len++;
  p = p->pNext;    //p指向下一结点
 }
 return len;
}

void sort(PNODE pHead)
{
 int len = getLength(pHead);  //获取链表长度   
 int i, j, t;     //用于交换元素值的中间变量
 PNODE p, q;      //用于比较的两个中间指针变量
 for(i=0,p=pHead->pNext ; i<len-1 ; i++,p=p->pNext)
 {
  for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
  {
   if(p->data > q->data)
   {
    t = p->data;
    p->data = q->data;
    q->data = t;
   }
  }
 }
 return;
}

bool insertElement(PNODE pHead, int pos, int val)
{
 int i = 0;
 PNODE p = pHead;
 //判断p是否为空并且使p最终指向pos位置的结点
 while(NULL!=p && i<pos-1)
 {
  p = p->pNext;
  i++;
 }
 if(NULL==p || i>pos-1)
  return false;
 //创建一个新结点
 PNODE pNew = (PNODE)malloc(sizeof(NODE));
 if(NULL == pNew)
 {
  printf("内存分配失败,程序退出!\n");
  exit(-1);
 }
 pNew->data = val;
 //定义一个临时结点,指向当前p的下一结点
 PNODE q = p->pNext;
 //将p指向新结点
 p->pNext = pNew;
 //将q指向之前p指向的结点
 pNew->pNext = q;
 return true;
}

bool deleteElement(PNODE pHead, int pos, int * pVal)
{
 int i = 0;
 PNODE p = pHead;
 //判断p是否为空并且使p最终指向pos结点
 while(NULL!=p->pNext && i<pos-1)
 {
  p = p->pNext;
  i++;
 }
 if(NULL==p->pNext || i>pos-1)
  return false;
 //保存要删除的结点
 * pVal = p->pNext->data;
 //删除p后面的结点
 PNODE q = p->pNext;
 p->pNext = p->pNext->pNext;
 free(q);
 q = NULL;
  return true;
}

 

 

  • 结尾语

上面实现的主要是单链表,另外还有双链表、循环链表、非循环链表等其他几种常见链表。双链表的特殊性表现在每个基本结点有两个指针域;循环链表的特性主要表现在,在循环链表中,通过任何一个结点可以找到其他所有结点。

4
0
分享到:
评论
1 楼 galwaycat00 2013-11-28  
看着这么眼熟,是不是郝斌老师的代码?你加上了注释,不错

相关推荐

    数据结构链表的c语言实现

    链表是一种基础且重要的...以上就是关于“数据结构链表的C语言实现”的详细知识,涵盖了链表的基础概念、类型、操作、C语言实现以及可能的应用。通过理解和掌握这些内容,可以更好地在实际编程中利用链表解决各种问题。

    数据结构C语言链表的实现

    数据结构C语言链表的实现

    数据结构之链表的实现

    线性表的存储结构使用链表。 2、提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、接收键盘录入的一系列整数(例10,25,8,33,60)作为节点的元素值,创建链表。输出链表内容。 4、输入...

    数据结构链表C语言实现

    链表是一种常见且重要的数据结构,尤其在C语言中被广泛使用。本篇文章将深入探讨链表的概念,以及如何使用C语言来实现链表的两种主要存储方式:尾接法和头接法。 首先,让我们理解链表的基本概念。链表不同于数组,...

    用数据结构-链表实现通讯录管理系统

    本项目以"用数据结构-链表实现通讯录管理系统"为主题,通过C语言实现了这一功能,旨在帮助用户管理他们的联系人信息。下面我们将深入探讨这个系统所涉及的主要知识点。 首先,我们来了解**链表**这一数据结构。链表...

    数据结构 链表操作 C语言实现

    根据给定的文件信息,我们可以总结出以下关于“数据结构链表操作C语言实现”的相关知识点: ### 一、链表的基本概念与定义 链表是一种线性数据结构,其中的元素不是在内存中连续存储的,而是通过指针链接在一起。...

    数据结构—链表的操作(C语言实现)

    数据结构,链表的各种操作(C语言实现),包含创建,销毁,置空等操作。

    通讯录管理系统数据结构C语言版链表实现实验报告.doc

    通讯录管理系统数据结构C语言版链表实现实验报告.doc

    单向链表c语言实现数据结构

    单向链表是一种基本的数据结构,它在计算机科学中被广泛应用。C语言是实现这种数据结构的理想工具,因为它的简洁性和灵活性。在这个话题中,我们将深入探讨如何使用C语言来创建和操作单向链表。 首先,单向链表是由...

    循环链表数据结构C语言实现

    下面我们将详细探讨循环链表的数据结构以及C语言中的实现方法。 首先,我们定义链表节点结构体。在C语言中,一个链表节点通常包含两个部分:数据和指向下一个节点的指针。对于循环链表,我们需要让最后一个节点的...

    数据结构-循环链表-C语言实现循环链表功能-数据结构学习

    C语言实现的数据结构中的循环链表 包含源码(.c文件),linux环境下编译生成的可执行文件,头文件 用于C语言以及数据结构的学习,熟练对循环链表边界的判定 实现了以下功能: 创建无头循环链表 向循环链表中插入...

    数据结构中十字链表的C语言实现

    根据给定的信息,本文将详细解释“数据结构中十字链表的C语言实现”这一主题。主要内容包括:十字链表的基本概念、十字链表在C语言中的实现方式、创建十字链表的过程、打印十字链表的方法以及两个十字链表相加的算法...

    数据结构---线性表之单链表(C语言)

    单链表是数据结构中的一种基础类型,尤其在C语言编程中经常被使用。它是一种线性的、非连续的数据组织形式,每...通过C语言实现,我们可以直观地理解链表的工作原理,这对于进一步学习高级数据结构和算法具有重要意义。

    数据结构-循环链表-C语言实现约瑟夫圈-数据结构学习

    C语言实现的数据结构中的循环链表 包含源码(.c文件),linux环境下编译生成的可执行文件,头文件,以及使用循环链表实现的约瑟夫圈的main.c文件 用于C语言以及数据结构的学习,熟练对循环链表边界的判定 此外循环...

    单链表(数据结构C语言版)

    单链表(数据结构C语言版) 链表的创建,插入,删除,排序等操作并建立有菜单,可以选择操作

    实现两个链表的合并(数据结构课程设计c语言版)

    实现两个链表的合并(数据结构课程设计c语言版)

    从尾到头打印链表(C语言实现)

    以上就是使用C语言实现从尾到头打印链表的方法,涉及到的主要知识点有链表的数据结构、链表节点的定义、链表反转的递归实现以及递归打印链表。这些概念和技能在数据结构与算法的学习中非常重要,对于理解和编写复杂...

    数据结构链表的插入与删除C语言的实现

    ### 数据结构链表的插入与删除C语言的实现 #### 概述 本文将详细介绍如何在C语言中实现单向链表的基本操作:插入和删除。链表是一种常见的线性表存储结构,它通过指针链接各个元素形成序列。与数组不同的是,链表中...

    数据结构 C语言版 线性表的动态存储结构之链表实现

    这是我上数据结构课时写的,在学线性表时,老师让我们写动态存储结构的线性表,所以我就写了这个链表

    C语言数据结构 静态链表

    静态链表的实现和操作 静态链表是一种常用的数据结构,静态链表是指在程序设计中,链表的结点是预先...本程序实现了静态链表的初始化、插入元素、删除元素、回收结点等操作,为后续的数据结构学习和应用提供了基础。

Global site tag (gtag.js) - Google Analytics