数据结构单链表的实现

最近正在恶补数据结构算法,大二上学期才学的 现在基本上式全还给老师 了 现在得拣起来 这几天也想了很多觉得自己就应该踏踏实实的努力 其他不要再想了 想得再多也没什么改变 关键是你自己得认识自己笨没关系,自知就好 知道应该笨鸟先飞 嗯 就这样了

我会把这个做成一个系列 一定要坚持下去 从线性表、栈、队列、串、二维数组、树和二叉树、图、排序、查找,现在想到就这么多了,嗯 洗把脸 开工了 !

链表的结点结构(觉得我写得不好可以直接看这里

┌──┬──┐
│data│next│
└──┴──┘
data域–存放结点值的数据域
next域–存放结点的直接后继的地址(位置)的指针域(链域)

tip:

1.链表通过结点的链域将线性表的结点按照逻辑顺序链接在一起

2.每个结点只有一个链域的链表为单链表Single Linked List

头指针head和终端结点指针域的表示

单链表每个结点的存储地址在结点域next中 开始结点没有前驱 头指针指向开始结点 终端结点的指针域不指向任何任何结点

tip:

链表由头指针唯一确定,单链表可以用头指针的名字来命名

单链表类型描述

[cce_cpp]
typedef char DataType; //假设结点的数据域类型为字符
typedef struct node{   //结点类型定义
DataType data;    //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList; //结构指针
ListNode *p;//结点指针
LinkList head;//头指针
[/cce_cpp]

tip:
①LinkList和ListNode *是不同名字的同一个指针类型(命名的不同是为了概念上更明确)
②LinkList类型的指针变量head表示它是单链表的头指针
③ListNode *类型的指针变量p表示它是指向某一结点的指针

下面是单链表主要操作:初始化操作,查找、插入、删除操作

程序参考了这里 这里

VS2008编译 运行通过

源代码 如下:

[cce_cpp]
#include <conio.h>//控制台输入输出Console Input/Output
#include <stdio.h>//标准输入输出头文件 standard input/output
#include <malloc.h>
#include <stdlib.h>//动态存储函数头文件

#define ERROR 0
#define OK 1
#define NULL 0
#define LEN sizeof(struct linkednode)//结构体的大小
typedef struct linkednode //定义单链表
{char data;
struct linkednode *next;
}Node,*Link_List;

Link_List create()//建立单链表
{
Link_List L;//定义结构指针
Node *p1,*p2;//定义结点
char data;
L=(Node*)malloc(LEN);//动态分配内存空间
p2=L;//将L的首地址赋值给p2
while((data=getchar())!='\n')//如果输入的不是回车 利用结点p1 p2将结点链接起来
{
p1=(Node*)malloc(LEN);//动态分配内存空间p1为移动的指针
p1->data=data;//赋值给data
p2->next=p1;//指定头指针p2的下一个结点为p1
p2=p1;//p2从头指针移动到p1
}
p2->next=NULL;//和谐最后一个结点的指针域
return L;
}
void printf(Link_List L)//输出单链表
{
Node *p;//声明结构指针
p=L->next;//头指针的第一个结点
while(p!=NULL)//循环输出
{printf("%c",p->data);
p=p->next;
}
printf("\n");
}
int ListIn(Link_List L,int i,char x)//在链表的第i个位置插入值为x的结点
{
Node *p,*s;//结构指针
int k;
p=L; //p指向头指针
k=0;
while(p!=NULL&&k<i-1)//判断链表不为空且p移动到i-1这个元素
{
p=p->next;
k++;
}
if(p==NULL||k!=i-1)//链表为空 则出错
{
printf("插入位置不存在:\n");
return ERROR;
}
s=(Node*)malloc(sizeof(Node));//为结构指针s分配内存空间
s->data=x;//为s赋值要插入的值
s->next=p->next;//将p的结点下一个地址赋值给s的指针域
p->next=s;//将s赋值给p结点的指针域
return OK;
}
int ListDel(Link_List L,int i)//删除链表的第i个结点
{
Node *p,*r;
int k;
p=L;
k=0;
while(p->next!=NULL && k<i-1)//链表不为空且p移动到i-1这个元素
{
p=p->next;
k++;
}
if(p->next==NULL&& k!=i-1)//链表为空 出错提示
{
printf("删除结点位置不合法:\n ");
return ERROR;
}
r=p->next;//要删除的结点指针
p->next=p->next->next;//将 i 的下一个结点地址赋值给 i -1 结点
free(r);//释放r 删除r
return OK;
}
char Find_List(Link_List L,int k)//在表中查找第k个元素 找到则返回该结点的指针 否则返回NULL
{        Link_List p;
int i;i=0;p=L->next;//初始化的时候执政指向第一个元素 i为计数器
while(p&&i<k)
{
p=p->next; i++;
}
if(p&&i==k) return p->data;//存在第k个元素 返回第k个元素
return NULL;
}

int main()//添加函数类型说明符
{
Link_List L=NULL;
char p;
char x;
int del_num,in_num,ser_num;
system("CLS");
printf("请输入链表结点:\n");
L=create();//创建链表
printf("请输入查找的结点位置:\n");
scanf("%d",&ser_num);
p=Find_List(L,ser_num);
printf("第%d个结点是%c\n",ser_num,p);
printf("请输入插入的结点值及插入位置:\n");
scanf("%c %d",&x,&in_num);
ListIn(L,in_num,x);//插入一个字符
printf("插入后的链表:\n");
printf(L);//输出链表
printf("请输入删除结点位置:\n");
scanf("%d",&del_num);
ListDel(L,del_num);//删除链表的元素
printf("删除后的链表为:\n");
printf(L);
system("pause");
}
[/cce_cpp]

链栈的实现

链栈由以下2个操作:入栈操作和出栈操作,创建2个函数,具体实现在下面:

[cce_cpp]
#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
char data;
struct Node *next;
}LstNode;

typedef LstNode *LStack;

LStack Push(LStack top,char x)
{
LstNode *temp;
temp=(LstNode*)malloc(sizeof(LstNode));
if(temp==NULL)
{
   printf("申请空间失败");
}
temp->data=x;
temp->next=top->next;
top->next=temp;
return (top);
}

char Pop(LStack top)
{
char x;
LstNode *temp;
if(top->next==NULL)
{
   printf("栈空无法出栈");
}
temp=top->next;
x=temp->data;
top->next=temp->next;
free(temp);
return (x);
}

main()
{
LStack LT;
char c;
LT=(LStack)malloc(sizeof(LstNode));
LT->next=NULL;
printf("请输入入栈字符:\n");
while((c=getchar())!='\n')
{
   LT=Push(LT,c);
}
printf("输出出栈字符:\n");
do
{
   c=Pop(LT);
   putchar(c);
}while(LT->next!=NULL);
printf("\n");
}
[/cce_cpp]
实现如下


链栈的实现
链栈的实现

顺序栈的实现

顺序栈由以下2个操作:入栈操作和出栈操作,创建2个函数,具体实现在下面:

[cce_cpp]
#include<stdio.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 50

typedef struct
{
char elem[Stack_Size];
int top;
}SeqStack;

int Push(SeqStack *S,char x)
{
if(S->top==Stack_Size-1)
   printf("栈已满无法进栈");
   S->top++;
   S->elem[S->top]=x;
   return (TRUE);
}
int Pop(SeqStack *S,char *x)
{
if(S->top==-1)
{
   printf("栈空无法出栈");
   return (FALSE);
}
else
{
   *x=S->elem[S->top];
   S->top--;
   return (TRUE);
}
}
void main()
{
SeqStack *ST;
char c1,*c2;
ST=(SeqStack*)malloc(sizeof(SeqStack));
c2=(char*)malloc(sizeof(SeqStack));
ST->top=-1;
printf("请输入字符:\n");
while((c1=getchar())!='\n')
{
   Push(ST,c1);
}
printf("输出出栈字符为:\n");
do
{
   Pop(ST,c2);
   putchar(*c2);
}
while(ST->top!=-1);

printf("\n");
}
[/cce_cpp]
实现如下


顺序栈的实现
顺序栈的实现