C语言实现双向链表

2024-10-23 01:11:06

这个小代码是我凭自己对指针和链表的理解和认识，自己实现的，没有参考其他人的代码，如果有相同的地方，那真的只是巧合，代码我在ubuntu 15.04下测试通过，可能存在很多错误和漏洞．

doublelist.c

/*************************************************************************
  > File Name: doublelist.c
  > Author: ChenYiLiang
  > Mail: chenyiliangex@163.com
  > Created Time: Sat 21 Mar 2015 07:32:22 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct userdata{
  int userid;
  char username[30];

  struct userdata *previous;
  struct userdata *next;
};

struct userdata *header;
size_t scanf_id;
char scanf_name[30];

int yesno;
int deletePosition;
int alterPosition;
int alterId;
char alterName[30];

int searchPosition;

FILE *ptr_fpid;

/*向链表中插入数据*/
int insert_list(struct userdata *header, size_t position, char name[], size_t id);
/*删除链表中指定的节点*/
int delete_node(struct userdata *header, size_t position);
/*修改指定位置的节点信息*/
int alter_node(struct userdata *header, size_t position, size_t id, char name[]);
/*查找链表中的数据*/
struct userdata *search_node(struct userdata *header, size_t position);
/*遍历链表*/
int travel_list(struct userdata *header);
/*判断链表是空*/
int isempty(struct userdata *header);

/*将链表结构写入文件*/
int write_into_file(struct userdata *header, FILE *fp);
/*从文件读取数据放到链表中*/
int read_from_file(struct userdata *header, FILE *fp);

int main(){
  struct userdata *header_node = (struct userdata *)malloc(sizeof(struct userdata));
  header_node -> previous = NULL;
  header_node -> next = NULL;

  read_from_file(header_node, ptr_fpid);
  travel_list(header_node);
  while(1){
  //scanf("%*[^\n]");
  //scanf("%*c");
  //scanf("%*[^\n]");
  printf("please input id - ");
  scanf("%d", &scanf_id);
  //scanf("%*c");
  //scanf("%*[^\n]");
  printf("please input your name - ");
  scanf("%s", scanf_name);

  printf("%d - %s\n\n", scanf_id, scanf_name);

  //isempty(header_node);

  /*0表示默认插入到链表的尾部*/
  insert_list(header_node, 0, scanf_name, scanf_id);

  //write_into_file(header_node, ptr_fpid);
  //isempty(header_node);

    printf("input anymore - ");
    scanf("%d", &yesno);
    if(yesno == -1){
      break;
    }

  scanf("%*c");
  scanf("%*[^\n]");
// travel_list(header_node);

  }
  getchar();
  //printf("delete position data - ");
  //scanf("%d", &deletePosition);
  //delete_node(header_node, deletePosition);

// printf("alter data for position - ");
// scanf("%d", &alterPosition);
// printf("please inout new id - ");
// scanf("%d",&alterId);
// printf("please input new name - ");
// scanf("%s", alterName);
// alter_node(header_node, alterPosition, alterId, alterName);
  write_into_file(header_node, ptr_fpid);
  travel_list(header_node);
  printf("\n\n");
  printf("please input position to search - ");
  scanf("%d", &searchPosition);
  struct userdata *searchData = search_node(header_node, searchPosition);
  printf("%d\n", searchData -> userid);
  printf("%s\n", searchData -> username);
  return 0;
}

/* 插入节点 */
int insert_list(struct userdata *header, size_t position, char name[], size_t id ){
  struct userdata *temp_newuser = header;
  struct userdata *getMemory = (struct userdata *)malloc(sizeof(struct userdata));

  getMemory -> userid = id;
  strncpy(getMemory -> username, name, 30);
  /*当position == 0时,表示默认插入到链表的尾部*/
  if(0 == position){
    if(NULL != temp_newuser -> next){
      while(NULL != temp_newuser -> next){
        temp_newuser = temp_newuser -> next;
      }
    }
  }

  /*当position > 1时则寻找合适的位置插入*/
  if(1 <= position){
    for(int i = 0; i <= position; i++){
      /*当执行此处的代码时表示,链表已经到达尾部或者是空链表*/
      if(NULL == temp_newuser -> next){
        break;
      }
      temp_newuser = temp_newuser -> next;
    }
  }

  getMemory -> previous = temp_newuser;
  if(temp_newuser -> next == NULL){
    temp_newuser -> next = getMemory;
    getMemory -> next = NULL;
  }else{
    temp_newuser -> next -> previous = getMemory;
    getMemory -> next = temp_newuser -> next;
    temp_newuser -> next = getMemory;
  }

  return 0;
}

/*删除链表中指定的节点*/
int delete_node(struct userdata *header, size_t position){
  int is_empty = isempty(header);
  if(0 == is_empty){
    printf("this si a empty list!\n\n");
    return -1;
  }

  struct userdata *deleteNode = header;

    for(int i = 0; i < position; i++ ){
      /*当执行此处的代码时表示,链表已经到达尾部或者是空链表*/
      if(NULL == deleteNode -> next){
        break;
      }
      deleteNode = deleteNode -> next;
    }

  /**/
  deleteNode -> next -> previous = deleteNode -> previous;
  deleteNode -> previous -> next = deleteNode -> next;
  free(deleteNode);

  return 0;
}

/*修改指定位置的节点信息*/
int alter_node(struct userdata *header, size_t position, size_t id, char name[]){
  int isEmpty = isempty(header);
  if(0 == isEmpty){
    printf("this is a empty list\n\n");
    return -1;
  }

  struct userdata *alterNode = header;
    for(int i = 0; i < position; i++ ){
      /*当执行此处的代码时表示,链表已经到达尾部或者是空链表*/
      if(NULL == alterNode -> next){
        break;
      }
      alterNode = alterNode -> next;
    }

    alterNode -> userid = id;
    strncpy(alterNode -> username, name, 30);

  return 0;
}

/*查找链表中的数据*/
struct userdata *search_node(struct userdata *header, size_t position){
  int isEmpty = isempty(header);
  if(0 == isEmpty){
    printf("this is a empty!\n");
    return NULL;
  }

  struct userdata *searchNode = header;
  for(int i = 0; i < position; i++){
    if(NULL == searchNode -> next){
      break;
    }
    searchNode = searchNode -> next;
  }

  return searchNode;
}

/*遍历链表*/
int travel_list(struct userdata *header){
  struct userdata *travel = header;
  if(NULL == travel -> next){
    printf("This is a empty list!!\n");
    return 1;
  }

  for(travel = travel -> next ; ; travel = travel -> next){
    printf("%d\n",travel -> userid);
    printf("%s\n", travel -> username);
    if(NULL == travel -> next){
      break;
    }
  }  

  return 1;
}

/*判断链表是空*/
int isempty(struct userdata *header){
  if(header -> next == NULL){
    return 0;
  }else{
    return 1;
  }
}

/*将链表结构写入文件*/
int write_into_file(struct userdata *header, FILE *fp){
  fp = fopen("listdata", "wb");
  if(NULL == fp){
    perror("open file failed when write into file!"),exit(-1);
  }

  printf("come into write!\n");
  for(struct userdata *move = header -> next; ; move = move -> next){
    fwrite(move,sizeof(struct userdata), 1, fp);
    if(NULL == move -> next){
      break;
    }
  }
  fclose(fp);
  fp = NULL;
  return 0;
}
/*从文件读取数据放到链表中*/
int read_from_file(struct userdata *header, FILE *fp){
  struct userdata *readfile = header;
  fp = fopen("listdata", "rb");
  if(NULL == fp){
    perror("open file failed when read - ");
    return -1;
  }

  while(1){
    struct userdata *newread = (struct userdata *)malloc(sizeof(struct userdata));
    fread(newread, sizeof(struct userdata), 1, fp);
    if(feof(fp)){/*当读取到文件的尾部时．跳出循环*/
      break;
    }
    readfile -> next = newread;
    newread -> next = NULL;
    newread -> previous = readfile;
    readfile = newread;
  }
  fclose(fp);
  fp = NULL;
  return 0;
}

C语言实现双向链表删除节点、插入节点、双向输出等操作

#include<cstdio>
#include<cstdlib>
typedef struct DoubleLinkedList
{
  int data;
  struct DoubleLinkedList *pre;
  struct DoubleLinkedList *next;
}DlinkedList_Node;
//建立链表
DlinkedList_Node* createDLink()
{
  DlinkedList_Node *head,*p,*s;
  int x;
  head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));
  p = head;
  while(1)
  {
    printf("please input the data: \n");
    scanf("%d",&x);
    if(x != 65535)
    {
      s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));
      s ->data = x;
      s-> pre = p;
      p->next = s;
      p=s;
    }
    else
      {
        printf("\n数据输入结束\n");
        break;
      }
  }
  p->next = NULL;
  head = head ->next;
  head->pre = NULL;
  return head;
}
//顺序、反序打印链表
void printDLink(DlinkedList_Node *head)
{
  DlinkedList_Node *p,*s;
  p = head;
  printf("正序输出双向链表：\n");
  while(p)
  {
    printf("%d ",p->data);
    s = p;
    p = p->next;
  }
  printf("\n 逆序输出双向链表: \n");
  while(s)
  {
    printf("%d ",s->data);
    s = s->pre;
  }
  printf("\n \n");
}
//删除一个结点
DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head,int i)
{
  DlinkedList_Node *p;
  p = head;
  if(p->data == i)
  {
    head = p->next;
    head->pre = NULL;
    free(p);
    return head;
  }
  while(p)
  {
    if(p->data == i)
    {
    p->pre->next = p->next;
    p->next->pre = p->pre;
    free(p);
    return head;
    }
    p = p->next;
  }
  printf("没有找到想要删除的数据\n");
  return head;
}
//插入一个结点
DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head,int i)
{
  DlinkedList_Node *p,*temp;
  p = head;
  temp = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));
  temp ->data = i;
  if(i < p->data)//比头结点数据小，插入到链表头部
  {
    head = temp;
    head->next = p;//此处p为原来的head
    head->pre = NULL;
    p->pre = head;//此处p为原来的head
    return head;
  }
  while(p != NULL && i > p->data)//寻找合适的插入位置
  {
    p = p->next;
  }
  if(i < p->data)//在链表中间某处找到合适插入位置
  {
    temp ->next = p;
    temp ->pre = p->pre;
    p ->pre->next = temp;
    p ->pre = temp;
    return head;
  }
  else//没有找到合适的位置，只有将数据插入到链表尾部
  {
    p->next = temp; //遍历到链表尾部，p==NULL
    temp ->pre = p;
    temp ->next = NULL;
    return head;
  }
}
int main()
{
  DlinkedList_Node *head;
  head = createDLink();
  printDLink(head);
  head = insertDlinkedList_Node(head,1012);
  head = deleteDlinkedList_Node(head,1991);
  printDLink(head);
}
/*****************************
运行结果如下：
please input the data:
1991
please input the data:
1992
please input the data:
2013
please input the data:
2014
please input the data:
512
please input the data:
420
please input the data:
65535 

数据输入结束
正序输出双向链表：
1991 1992 2013 2014 512 420
 逆序输出双向链表:
420 512 2014 2013 1992 1991 

正序输出双向链表：
1012 1992 2013 2014 512 420
 逆序输出双向链表:
420 512 2014 2013 1992 1012 

******************************/

以上就是本文给大家分享的全部内容了，希望对大家更加熟悉C语言双向链表能够有所帮助。

C语言数据结构双向链表的建立与基本操作

C语言数据结构双向链表的建立与基本操作双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作由于定义双向链表时指针域中
C语言实现数据结构和双向链表操作

数据结构双向链表的实现双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址. 双向链表结点的类型描述: //双向链表的类型描述 typedef int ElemType; typedef struct node{ ElemType data; struct node *prior,*next; }DuLNode,*DuLinkList; 其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址. 双
C语言双向链表的表示与实现实例详解

1.概述: C语言中一种更复杂的链表是"双向链表"或"双面链表".其表中的每个节点有两个连接:一个指向前一个节点,(当这个"连接"为第一个"连接"时,指向空值或者空列表):而另一个指向下一个节点,(当这个"连接"为最后一个"连接"时,指向空值或者空列表) 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接在一些低级语言中, XOR-linking 提供一种在双向链表中
C语言之双向链表详解及实例代码

1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <
C语言双向链表实现根据使用频率安排元素位置的功能实例代码

C语言双向链表应用前言: 平时使用音乐播放器时,播放列表中的歌曲可以很方便地进行增添,删除,去重等操作.但其本质都可以抽象成一个双向链表.为了更方便用户的使用,我认为还可以增加一个将最常播放的音乐放在播放列表的头部的功能,那么如何实现呢? 请看代码: #include<stdio.h> #include<stdlib.h> #include<time.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALS
C语言数据结构双向链表简单实例

双向链表的基本操作 1．利用尾插法建立一个双向链表. 2．遍历双向链表. 3．实现双向链表中删除一个指定元素. 4．在非递减有序双向链表中实现插入元素e仍有序算法. 5．判断双向链表中元素是否对称若对称返回1否则返回0. 6．设元素为正整型,实现算法把所有奇数排列在偶数之前. 7．在主函数中设计一个简单的菜单调试上述算法. 实例代码: //排序的时候因为没有说明奇数和偶数需不需要各自再排序,我就没有排序,只是将奇数放在偶数后面. //创建链表的时候,因为这个实验没有要求输出链表的长度,所以我就输
C语言实现双向链表

这个小代码是我凭自己对指针和链表的理解和认识,自己实现的,没有参考其他人的代码,如果有相同的地方,那真的只是巧合,代码我在ubuntu 15.04下测试通过,可能存在很多错误和漏洞． doublelist.c /************************************************************************* > File Name: doublelist.c > Author: ChenYiLiang > Mail: chenyilian
C语言中双向链表和双向循环链表详解

双向链表和双向循环链表和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =
Java中双向链表详解及实例

Java中双向链表详解及实例写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin
C语言实现的双链表功能完整示例

本文实例讲述了C语言实现的双链表功能.分享给大家供大家参考,具体如下: Dlist.h #ifndef __DLIST_H__ #define __DLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { ElemType data; struct Node *prio; struct Node *next; }
Java语言中链表和双向链表

链表是一种重要的数据结构,在程序设计中占有很重要的地位.C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构.Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点. class Node { Object data; Node next;//指向下一个结点 } 将数据域定义成Object类是因为

C语言实现双向链表

相关推荐

随机推荐