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工程文件，这对于学习和理解数据结构有着极大的帮助。 首先，我们要明确数据结构的重要性。数据结构是计算机存储、组织数据的方式，它决定了数据...
数据结构课程设计航空客运订票系统源代码+报告文档和可执行文件数据结构课程设计航空客运订票系统源代码+报告文档和可执行文件数据结构课程设计航空客运订票系统源代码。数据结构课程设计航空客运订票系统源代码+...
《郝斌 数据结构源代码和数据结构 大纲》是一个针对数据结构学习的重要资源集合，主要包含源代码和教学大纲，旨在帮助学习者深入理解数据结构的原理与应用。数据结构是计算机科学中的核心课程，它研究如何在计算中...
c++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构代码.zipc++代码数据结构...
《C++数据结构源代码详解》 数据结构是计算机科学中的基础学科，它研究如何高效地组织和存储数据，以便于我们对数据进行快速访问和操作。C++作为一门强大的编程语言，是实现数据结构的理想工具，其面向对象的特性...
严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar严蔚敏数据结构源代码.rar
《清华大学数据结构代码详解》 数据结构是计算机科学中的核心课程之一，它是研究如何高效地组织和存储数据以便于访问和处理。清华大学的这组数据结构代码由C++语言编写，出自计算机系邓俊辉老师的课程，对于学习者...
"郝斌数据结构代码"是一个学习资源，可能包含了郝斌老师对于各种经典数据结构实现的代码示例，这些代码通常使用常见的编程语言如C、C++或Java编写。 以下是这个资源可能涵盖的一些关键数据结构及其重要知识点： 1....
这个名为“浙大数据结构代码”的压缩包文件，很显然是为了配合Weiss的教材，提供了C语言实现的数据结构代码示例。 首先，我们要理解C语言是一种底层编程语言，它对于理解和实现数据结构的细节非常有利。C代码可以...
数据结构代码集合 数据结构是计算机科学中的一门重要基础学科，它研究的是数据的存储、表示和操作。数据结构代码集合是指对各种数据结构的代码实现，包括线性表、栈、队列、树、图等。这些数据结构是计算机科学的...
数据结构（C语言版）--清华大学出版社，配套代码有助于你的学习。学习数据结构，并不仅仅是学习其中现成的那些队列，堆栈，二叉树，图等经典结构， 也不仅仅是学习其中的那些快速排序、冒泡排序等算法。《数据结构》...
陈越老师的《数据结构》第二版是一本深受学生和专业人士欢迎的教材，其配套的源代码为学习者提供了实践和理解数据结构算法的宝贵资源。在这个压缩包中，包含了书中的所有程序源代码，分为.txt（伪代码）和.c（C语言...
这份“数据结构教程ppt和源代码”资料包为学习者提供了全面的学习资源，包括理论讲解和实践操作，对于深入理解和掌握数据结构至关重要。 首先，我们来看“数据结构教程第五版 PPT”。PPT文件通常包含精心设计的幻灯...
本压缩包包含了书中所有的源代码实现，帮助读者深入理解数据结构的原理并提升编程能力。 首先，我们来了解一下数据结构的基本概念。数据结构是数据的逻辑组织形式，包括线性结构（如数组、链表）、树形结构（如...