用C语言实现单链表的各种操作(一)

最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的《数据结构》(C 语言版),中的例子和后面的习题进行改编的。首先,是单链表的各种实现,其中,包含了一些常考的知识点。例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现。
下面这个是单链表的结构体的定义:


代码如下:

typedef struct LNode
{
 ElemType data;
 struct LNode *next;
}LinkList;

下面的基本的单链表的操作:其中,有一些宏,没有给出他们的一些定义,者可以通过,严蔚敏的《数据结构》(C 语言版),查看得到。


代码如下:

/* 功能:构建一个空的带头节点的单链表*/
Status InitList (struct LNode **L)
{
  (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点
  if(!*L)
   exit(OVERFLOW);
  (*L)->next = NULL;
  return OK;
}
/*销毁线性表*/
Status DestroyList(struct LNode *L)
{
  struct LNode *q;
  while(L)
  {
    q = L->next;
    free(L);
    L = q;
  }
  return OK;
}
/*将L重置为空表*/
Status ClearList(struct LNode *L)
{
  LinkList *p,*q;
  p = L->next;
  while(p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL;
  return OK;
}
/*判断链表是否为空表*/
Status ListEmpty(LinkList *L)
{
  if(L->next)
  {
    return FALSE;
  }
  else
  {
    return TRUE;

}
}
/*返回单链表中元素的个数*/
int ListLength(struct LNode *L)
{
  int i=0;
  LinkList *p = L->next;
  while(p)
  {
    i++;
    p = p->next;
  }
  return i;
}
/* L为带头节点的单链表的头指针,当第i个元素存在时,其值赋给e,并返回OK */
Status GetElem(struct LNode *L,int i,ElemType *e)
{
  int j=1;
  LinkList *p = L->next;
  while(p && j<i)
  {
    p = p->next;
    j++;
  }
  if(!p || j>i)
    return ERROR;
  *e = p->data;
  return OK;
}
/*返回L中第一个与e满足关系compare()的数据元素的位序,
 若给存在返回值为0,compare()是数据元素的判定函数*/
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
  int i =0;
  LinkList *p = L->next;
  while(p)
  {
    i++;
    if(compare(p->data,e))
      return i;
    p=p->next;
  }
  return 0;
}

代码如下:

/*所cur_e是L中的数据元素,且给就第一个,则用pre_e返回它的前驱*/
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
  LinkList *q,*p=L->next;
  while(p->next)
  {
    q = p->next;//q指向p的后继
    if(q->data == cur_e)
    {
      *pre_e = p->data;
      return OK;
    }
    p = q;
  }
  return INFEASIBLE;

}
/* 若cur_e是L中的数据元素,且不是最后一个,则用next_e返回它的后继*/
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
  LinkList *p;
  p = L->next;
  while(p->next)
  {
    if(p->data == cur_e)
    {
     * next_e = p->next->data;
      return OK;
    }
    p = p->next;
  }
  return INFEASIBLE;
}
/* 在带头节点的单链表L中的第i个位置之前插入元素e*/
Status ListInsert(struct LNode *L,int i,ElemType e)
{
  int j =0;
  struct LNode *p=L,*s=NULL;
  while(p && j<i-1)
  {
    p=p->next;
    j++;
  }
  if(!p || j>i-1)
    return ERROR;
  s = (struct LNode *)malloc(sizeof(struct LNode));
  if(!s)
    printf("malloc error~\n");
  // p->next = s;
  s->data = e;
  // p->next = s;
   s->next = p->next;
   p->next = s;
   //s->next = NULL;
  // p = s;
  return OK;
}
/*在带头节点的单链表中删除第i个元素,并有e返回其值*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{

LinkList *p=L,*q;

int j=0;
  while(p->next && j< i-1)
  {
    p = p->next;
    j++;
  }
  if(!p->next || j>i-1)
    return ERROR;
  q = p->next;
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
  }
/* 依次对L的每个元素调用vi(),打印输出语句*/
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
  LinkList *p = L->next;
  while(p)
  {
    vi(p->data);
    p = p->next;
  }
  printf("\n");
  return OK;
}

(0)

相关推荐

  • 用C语言实现单链表的各种操作(二)

    上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序. 复制代码 代码如下: /* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){  LinkList *p;  int n,i,j;  int temp;  n = ListLength(head);  if(head == NULL || head->next == NULL)    return head; 

  • C语言实现单链表实现方法

    C语言实现单链表实现方法 链表和我们之前实现过的顺序表一样,都是简单的数据结构,链表分为单向链表.双向链表.循环链表.而单向链表又分为两种实现方法,一种为带头节点的单链表,一种为不带头节点的单链表.我们来具体看看不带头节点的单链表的实现 单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点. 今天我们来实现一些单链表的简单接口 先看看单链表的结构: (为了通用性,我们将类型重命名为DataType) typedef int DataType; //

  • 数据结构 C语言实现循环单链表的实例

    数据结构 C语言实现循环单链表的实例 实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环

  • c语言实现单链表算法示例分享

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>typedef char DataType;typedef struct Node{    DataType data;    struct Node * Next;}ListNode,* LinkList;void Judement(LinkList head){ //判断分配内存    if (!head){        printf("Overflow.");

  • C语言之单链表的插入、删除与查找

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.要实现对单链表中节点的插入.删除与查找的功能,就要先进行的单链表的初始化.创建和遍历,进而实现各功能,以下是对单链表节点的插入.删除.查找功能的具体实现: #include<stdio.h> #include<stdlib.h> #include<string.h> typedef int ElemType; /** *链表通用类型 *ElemType 代表自定义的数据类型 *struct

  • C语言单链表实现多项式相加

    本文实例为大家分享了C语言单链表实现多项式相加的具体代码,供大家参考,具体内容如下 //多项式的相加和相乘 #include<stdio.h> #include<stdlib.h> #pragma warning(disable:4996)//兼容scanf typedef struct node { int coef; int expon; struct node* link; }Polynode,*Polynomial; Polynomial InsertPolyLinklis

  • C语言创建和操作单链表数据结构的实例教程

    1,为什么要用到链表 数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性.但数组也同样存在一些弊病.如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一.我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费. 我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要.链表就是我们需要的动态数组.它是在程序的执行过程中根据需要有数据存储就向系统要求

  • C语言单链表常见操作汇总

    C语言的单链表是常用的数据结构之一,本文总结了单链表的常见操作,实例如下: #include<stdio.h> #include<stdlib.h> //定义单链表结构体 typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }LNode,*LinkList; //创建单链表 void Build(LinkList L) { int n; LinkList p,q; p=L; pr

  • C语言实现单链表逆序与逆序输出实例

    单链表的逆序输出分为两种情况,一种是只逆序输出,实际上不逆序:另一种是把链表逆序.本文就分别实例讲述一下两种方法.具体如下: 1.逆序输出 实例代码如下: #include<iostream> #include<stack> #include<assert.h> using namespace std; typedef struct node{ int data; node * next; }node; //尾部添加 node * add(int n, node * h

  • C语言单链表的实现

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表结构: SList.h #pragma once typedef int DataType; typedef struct SListNode { DataType data; struct SListNode* next; }SListNode; // 如果要修改链表就必须加引用 SListNode* _BuyNode(DataType x); //建立节点 void PrintSlist(SListNode

随机推荐