1、链表代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}LinkNode,*List,*Position;
List init()
{
List s;
s = (List)malloc(sizeof(LinkNode));
s->data = 0;
s->next = NULL;
return s;
}
void destory(List s)
{
List p;
p = s;
while(p->next)
{
s = s->next;
free(p);
p = s;
}
}
void insert(List s,int pos,int e)
{
int i = 1;
//s = s->next;
while(s&&(i!=pos))
{
s = s->next;
i++;
}
List p = (List)malloc(sizeof(LinkNode));
p->data = e;
p->next = s->next;
s->next = p;
}
void del(List s,int pos,int e)
{
int i = 1;
//s = s->next;
while(s&&(i!=pos))
{
s = s->next;
i++;
}
List p = s->next;
s->next = p->next;
free(p);
}
void show(List s)
{
s = s->next;
while(s)
{
printf("%d",s->data);
s = s->next;
}
}
int main()
{
List s = init();
insert(s,1,5);
insert(s,2,6);
insert(s,3,7);
insert(s,4,9);
insert(s,5,34);
show(s);
return 0;
}
2、链表操作
#include <stdio.h>
#include <iostream>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n)
{
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
for (int i=n;i>0;--i)
{
LinkList p=(LinkList)malloc(sizeof(LNode));
printf("输入插入到链表的元素\n");
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
int GetElem(LinkList &L,int i)
{
LinkList p=L->next;
int j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if (!p&&j>i)
return -1;
int e=p->data;
printf("得到的第%d元素为%d\n",i,e);
return 1;
}
int InsertList(LinkList &L,int i,int e)
{
LinkList p=L;
int j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if (!p&&j>i)
return -1;
LinkList s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
printf("插入元素位置%d，插入元素为%d\n",i,e);
return 1;
}
int DeleteList(LinkList &L,int i,int e)
{
LinkList p=L,q;
int j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if (!p&&j>i-1)
return -1;
q=p->next;
p->next=q->next;
e=q->data;
printf("删除元素位置%d，删除元素为%d\n",i,e);
free(q);
return 1;
}
void Length(LinkList &L)
{
int i=0;
LinkList p=L->next;
while(p)
{
++i;
p=p->next;
}
printf("长度为%d\n",i);
}
void Desplay(LinkList &L)
{
LinkList p=L->next;
while(p)
{
printf("链表中的元素为%d\n",p->data);
p=p->next;
}
}
//归并两个链表需要逆序输入
void MergeList(LinkList &la,LinkList &lb,LinkList &lc)
{
LinkList pa=la->next;
LinkList pb=lb->next;
LinkList pc=la;
lc=pc;
while(pa&&pb)
{
if (pa->data<pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
printf("归并后的链表\n");
free(lb);
}
//反转一个单链表
void ReverseLink(LinkList &L)//有点问题
{
if(L==NULL)
exit(-1);
LinkList curr,prev=NULL,temp;
curr=L;
while(curr->next)
{
temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
curr->next=prev;
Desplay(curr);
free(temp);
}
void main()
{
LinkList L;
LinkList lb,lc;
int n=0;
printf("输入插入到链表的元素个数\n");
scanf("%d",&n);
CreateList(L,n);
printf("输入插入到链表的元素个数\n");
scanf("%d",&n);
CreateList(lb,n);
MergeList(L,lb,lc);
Desplay(lc);
printf("反转一个单链表\n");
ReverseLink(L);
InsertList(L,1,1);
InsertList(L,2,3);
InsertList(L,3,5);
DeleteList(L,1,1);
GetElem(L,1);
Desplay(L);
Length(L);
system("pause");
}
3、顺序表
#include <stdio.h>
#include <iostream>
typedef int ElemType;
#define LIST_ININ_SIZE 100
#define LIST_INCREASE 10
typedef struct
{
ElemType *elem;
int length;
int listsize;
}Sqlist;
int InitList(Sqlist &L)
{
L.elem=(ElemType*)malloc(sizeof(ElemType)*LIST_ININ_SIZE);
if (!L.elem)
exit(-1);
L.length=0;
L.listsize=LIST_ININ_SIZE;
return 1;
}
int InsertList(Sqlist &L,int i,ElemType e)
{
if (i<1||i>L.length+1)
return -1;
if (i>=L.listsize)
{
ElemType *newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREASE)*sizeof(ElemType));
if (!newbase)
exit(-1);
L.elem=newbase;
L.listsize+=LIST_INCREASE;
}
ElemType *p,*q;
q=&L.elem[i-1];
for (p=&L.elem[L.length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
printf("插入位置%d,插入元素为%d,线性表的长度%d\n",i,e,L.length);
return 1;
}
int DeleteList(Sqlist &L,int i,ElemType e)
{
if (i<1||i>L.length)
return -1;
ElemType *p,*q;
p=&L.elem[i-1];
e=*p;
q=L.elem+L.length-1;
for(++p;p<q;++p)
*(p-1)=*p;
--L.length;
printf("删除位置%d,删除元素为%d,线性表的长度%d\n",i,e,L.length);
return 1;
}
void main()
{
Sqlist L;
InitList(L);
InsertList(L,1,1);
InsertList(L,2,2);
InsertList(L,3,3);
DeleteList(L,1,1);
DeleteList(L,2,2);
system("pause");
}
4、栈
#include <stdio.h>
#include <iostream>
typedef int ElemType;
#define STACK_ININ_SIZE 100
#define STACK_INCREASE 10
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(sizeof(ElemType)*STACK_ININ_SIZE);
if(!S.base)
return -1;
S.top=S.base;
S.stacksize=STACK_ININ_SIZE;
return 1;
}
void GetTop(SqStack S)
{
if(S.top==S.base)
exit(-1);
int e=*(S.top-1);
printf("栈顶元素%d\n",e);
}
void Push(SqStack &S,int e)
{
if (S.top-S.base>=STACK_ININ_SIZE)
{
S.base=(ElemType*)realloc(base,sizeof(ElemType)*(STACK_ININ_SIZE+S.stacksize));
S.top=S.stacksize+S.base;
S.stacksize+=STACK_INCREASE;
}
*S.top++=e;
printf("元素%d入栈\n",e);
}
void Pop(SqStack &S)
{
if(S.top==S.base)
exit(-1);
int e=*--S.top;
printf("元素%d出栈\n",e);
}
void main()
{
SqStack S;
InitStack(S);
Push(S,0);
Push(S,2);
Push(S,3);
Pop(S);
Pop(S);
GetTop(S);
system("pause");
}
5、队列
#include <stdio.h>
#include <iostream>
typedef int ElemType;
typedef struct QNode
{
struct QNode *next;
ElemType data;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &q)
{
q.front=q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!q.front)
exit(-1);
q.front->next=NULL;
}
int EnQueue(LinkQueue &q,int e)
{
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if (!p)
return -1;
p->data=e;
p->next=NULL;
q.rear->next=p->next;
q.rear=p;
printf("元素%d入队\n",e);
return 1;
}
int DeQueue(LinkQueue &q,int e)
{
if(q.front==q.rear)
return -1;
QueuePtr p=q.front->next;
q.front->next=p->next;//有问题
if (q.rear==p)
q.rear=q.front;
printf("元素%d出队\n",e);
free(p);
return 1;
}
void main()
{
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,1);
EnQueue(Q,2);
DeQueue(Q,1);
system("pause");
}
6、二叉树
#include <iostream>
using namespace std;
typedef char EmleType;
typedef struct BitNode
{
EmleType data;
struct BitNode *rchild,*lchild;
}BitNode,*BiTree;
void CreateTree(BiTree &T)
{
char ch;
//abc de g f
scanf("%c",&ch);
if(ch=='*')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BitNode));
if(!T)
exit(-1);
T->data=ch;
CreateTree(T->lchild);
CreateTree(T->rchild);
}
}
void PreOrder(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
PreOrder(T->lchild);
printf("%c",T->data);
PreOrder(T->rchild);
}
}
void PosOrder(BiTree T)
{
if(T)
{
PreOrder(T->lchild);
PreOrder(T->rchild);
printf("%c",T->data);
}
}
void main()
{
BiTree T;
CreateTree(T);
PreOrder(T);
InOrder(T);
PosOrder(T);
system("pause");
}
7、循环链表的判断
#include <stdio.h>
#include <iostream>
typedef struct LNode//判断链表是否存在环
{
char data;
struct LNode *next;
}*Link;
int LinkCircle(Link head)
{
Link p=head;
Link p1=head->next;
if (head==NULL||head->next==NULL)
return 0;
if (head=head->next)
return 1;
while(p!=p1&&p!=NULL&&p1->next!=NULL)
{
p=p->next;
p1=p1->next->next;
}
if(p==p1)
return 1;
else return 0;
}
void main()
{
Link p1,p2,p3,p4;
p1=(Link)malloc(sizeof(LNode));
p2=(Link)malloc(sizeof(LNode));
p3=(Link)malloc(sizeof(LNode));
p4=(Link)malloc(sizeof(LNode));
p1->next=p2;
p2->next=p3;
p3->next=p4;
p4->next=p1;
if (LinkCircle(p1))
printf("is circle\n");
else
printf("is not circle\n");
system("pause");
}
8、判断两个单链表是否交叉及查找交叉点位置
问题1：如何判断俩单链表（俩单链中均无环）是否交叉？
第一条链遍历至尾部，记此结点指针为p1；第二条链也遍历至尾部，此记结点指针为p2。则若此时p1与p2相等，俩单链交叉。函数可写如下：
#include <stdio.h>
struct LNode
{
int data;
struct LNode *next;
};
void IsCross(LNode *head1,LNode *head2)
{
LNode *p1=head1->next;
while(p1->next)
{
p1=p1->next;
}
LNode *p2=head2->next;
while(p2->next)
{
p2=p2->next;
}
if(p1=p2)
{
printf("Two link lists intersecting.");
}else
{
printf("Two link lists are not intersecting.");
}
}
问题2：如果交叉，如何找到交叉点？ 若较长链表为head1。设两指针p1和p2分别对链表head1和head2从头遍历，步长均为1，让p1先移动nLen1 - nLen2步，再让p1和p2同时移动，则p1与p2相遇处即为交叉点处。函数可写如下：
LNode *findCross(LNode *head1, int nlen1,LNode *head2, int nlen2)
{
LNode *p1=head1, *p2=head2;
int diffLen = nlen1-nlen2;
if(diffLen>0)
{
while(diffLen>0)
{
p1=p1->next;
diffLen--;
}
}else
{
while(diffLen<0)
{
p2=p2->next;
diffLen--;
}
}
while(p1!=p2)
{
p1=p1->next;
p2=p2->next;
}
return p1;
}
相关推荐
《李春葆数据结构源代码》是一份宝贵的教育资源，它为学习数据结构提供了直观的实践素材。李春葆教授在第三版的教材中深入浅出地讲解了数据结构这一计算机科学的基础概念，而源代码正是理论知识的具体实现，是理解和...
本压缩包包含的数据结构源代码涵盖了多个关键主题，包括树、图、字符串处理、排序算法、哈希表以及路径查找算法。下面将详细讨论这些知识点。 1. **树的遍历**： - **一般树的遍历**：树是一种非线性数据结构，...
"考研王道数据结构代码.zip"这个压缩包包含了2020年王道数据结构课程的课后习题代码，对于考生来说是一个宝贵的参考资料。 王道数据结构教材以其清晰易懂的讲解和丰富的例题著称，其配套的可执行代码可以帮助学生更...
这里提到的代码实现是基于C++语言，实现了书中讲解的多种数据结构和算法。 1. **线性表**：线性表是一种基本的数据结构，由n（n>=0）个相同类型元素构成的有限序列。代码中提供了顺序表示的线性表，通过结构体`node...
数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip数据结构考试代码.zip...
本压缩包包含了邓俊辉老师编写的全部源代码以及对应的Visual Studio工程文件，这对于学习和理解数据结构有着极大的帮助。 首先，我们要明确数据结构的重要性。数据结构是计算机存储、组织数据的方式，它决定了数据...
上海交通大学的数据结构作业代码集合是一份宝贵的教育资源，涵盖了多种数据结构和算法的实践应用。这份作业涉及了数据结构课程中的核心概念，包括数组、链表、树、图、栈、队列、排序和查找等。以下是对每个指定作业...
在解题过程中，你可能会遇到一些挑战，但通过反复实践，可以更好地掌握数据结构的精髓。 压缩包中的"目录.png"可能是一个文件结构的可视化表示，它展示了所有代码文件和子目录的层次关系，帮助用户快速定位到特定的...
《郝斌 数据结构源代码和数据结构 大纲》是一个针对数据结构学习的重要资源集合，主要包含源代码和教学大纲，旨在帮助学习者深入理解数据结构的原理与应用。数据结构是计算机科学中的核心课程，它研究如何在计算中...
本文将深入探讨由殷人昆编写的C++版数据结构代码，以及它们所涵盖的关键知识点。 首先，我们要理解C++中的基本数据类型，如int、char、float等，它们是构建更复杂数据结构的基础。在殷人昆的代码中，你会看到如何...
c++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构...
《C++数据结构源代码详解》 数据结构是计算机科学中的基础学科，它研究如何高效地组织和存储数据，以便于我们对数据进行快速访问和操作。C++作为一门强大的编程语言，是实现数据结构的理想工具，其面向对象的特性...
《清华大学数据结构代码详解》 数据结构是计算机科学中的核心课程之一，它是研究如何高效地组织和存储数据以便于访问和处理。清华大学的这组数据结构代码由C++语言编写，出自计算机系邓俊辉老师的课程，对于学习者...
严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar
《严蔚敏数据结构代码全集》是一份珍贵的学习资源，专为计算机科学和技术领域的学生、教师以及自我学习者提供。这份压缩包包含了严蔚敏教授编写的《数据结构》一书中的全部代码实现，使用C语言编写，同时附带了相关...
数据结构常用代码、、很全很有用， 适合初学者借鉴
这个压缩包“数据结构代码大全”显然是为学习者提供了一个全面的数据结构算法的资源库，特别适合那些正在准备期末考试或考研的学生。以下是关于这个主题的详细知识点： 1. **数据结构基础**：数据结构是一门研究...
陈越老师的《数据结构》第二版是一本深受学生和专业人士欢迎的教材，其配套的源代码为学习者提供了实践和理解数据结构算法的宝贵资源。在这个压缩包中，包含了书中的所有程序源代码，分为.txt（伪代码）和.c（C语言...
以下是关于数据结构的一些关键知识点： 1. **数组**：是最基本的数据结构，它是一个元素类型相同的固定大小的序列，可以通过索引访问。数组的访问速度快，但插入和删除操作复杂度较高。 2. **链表**：由一系列节点...
数据结构代码集合 数据结构是计算机科学中的一门重要基础学科，它研究的是数据的存储、表示和操作。数据结构代码集合是指对各种数据结构的代码实现，包括线性表、栈、队列、树、图等。这些数据结构是计算机科学的...