安科网

数据结构的一些代码

妖怪哪里跑

妖怪哪里跑

2013-04-15

关注 关注

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;
}

数据结构 next

妖怪哪里跑

妖怪哪里跑

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

详解Redis数据结构之跳跃表

我们先不谈Redis，来看一下跳表。还要支持输入道具名称的精确查询和不输入名称的全量查询。拍卖行商品列表是线性的，最容易表达线性结构的是数组和链表。每个元素均关联一个double类型的score，Redis 根据score进行从小到大排序；这个是 Redi

koushr 2020-11-12

数据结构之利用PHP实现二分搜索树

二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。二叉树不一定是满的，可能只有左儿子或又儿子。

KAIrving 2020-10-25

泛型和元编程的模型：Java, Go, Rust, Swift, D等

在程序设计的时候，我们通常希望使用同样的数据结构或算法，就可以处理许多不同类型的元素，比如通用的List或只需要实现compare函数的排序算法。在本文中，我将带你领略不同语言中的泛型系统以及它们是如何实现的。我将从C这样的不具备泛型系统的语言如何解决这个

zhangxiafll 2020-11-13

万能Python的秘诀：操纵数据的内置工具

本文转载自公众号“读芯术”。Python可谓是如今最流行的编程语言，甚至孩子们也可以从它开始学习趣味编程。Python类似英语的简单语法使它成为一种通用语言，已在全世界各个领域被广泛使用。Python的万能之处正在于其内置的数据结构，它使编码变得简单，不受

kikaylee 2020-10-31

Java实现单链表、栈、队列三种数据结构

它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap等等的底层都是用链表实现的。添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将

范范 2020-10-28

Map和Set两种数据结构在ES6的作用

什么又是字典呢？每个元素有一个称作key 的域，不同元素的key 各不相同。它们之间又有什么区别呢？大多数主流编程语言都有多种内置的数据集合。然而 JavaScript 直到ES6的发布之前，只拥有数组和对象这两个内建的数据集合。Set中的元素只会出现一次

MILemon 2020-10-22

「算法与数据结构」带你看回溯算法之美

我对回溯算法有一定理解：回溯算法建立在DFS基础之上的，但不同的是在搜索的过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索，因此我们可以这样子理解，回溯算法与DFS的区别就是有无状态重置。如果你还不了解什么是回溯算法，或者知道一些，但是对于它具体是如

hugebawu 2020-10-12

比较JavaScript中的数据结构（数组与对象）

在编程中，如果你想继续深入，数据结构是我们必须要懂的一块， 学习/理解数据结构的动机可能会有所不同，一方面可能是为了面试，一方面可能单单是为了提高自己的技能或者是项目需要。无论动机是什么，如果不知道什么是数组结构及何时使用应用字们，那学数据结构是一项繁琐

LauraRan 2020-09-28

学c++需要先学c语言吗？

看需求，如果是底层开发，就必须学习C语言。如果只是应用开发，可以直接从C++开始学习。实际上这两个语言是平等的，只是在语法上C++尽量与C兼容，但仍然有很多不同的地方。1) C++不是C的超集。2) 如果你选择了一本好书，学C++之前完全没有必要学C，即使

shenwenjie 2020-09-24

动图演示：手撸堆栈的两种实现方法！

正式开始之前，先和各位朋友聊聊公众号后期的一些打算，后面的文章计划写一些关于数据结构和算法的内容，原因很简单「底层结构决定上层建筑嘛」，对于框架满天飞的今天，我们不止要学习如何使用框架，更要了解它的原理以及底层数据结构，只有这样我们才能更好的应用它。当然，

omyrobin 2020-09-23

技术人员思维和认知升级

今天这篇文章准备整理下我原来谈过的和技术人员相关的思维方面的话题，整个内容实际上包括两个方面。其一是我们可以从开发和技术中借鉴哪些思维方式；其二是技术人员本身不要受限于技术中，而应该跳出盒子培养价值驱动下的经营思维。结构化思维是架构思维必须具备的，最常用的

guangcheng 2020-09-22

python的链表基础知识点

python中的链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表有两种类型：单链表和双链表。一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中，相反，你可以通过一个节点指向另外一个

qiangde 2020-09-13

数据结构 4

//顺序表的插入操作 bool ListInsert { if//判断i的范围是否合法 return false if//存储空间是否满了 return false; //开始插入元素 for{ L.data[j] = L.dat

hanyujianke 2020-08-18

HBase/TiDB都在用的数据结构：LSM Tree，不得了解一下？

LSM Tree广泛应用在HBase，TiDB等诸多数据库和存储引擎上，我们先来看一下它的一些应用：。这么牛X的名单，你不想了解下LSM Tree吗？装X之前，我们先来了解一些基本概念。设计数据存储系统可能需要考虑的一些问题有：ACID，RUM。读性能体现

晨曦之星 2020-08-14

编写更简洁的Python代码的5个技巧

许多人刚开始学习编程时会选择Python。Python确实是初学者友好的。当您按照其官方网站上的下载和安装说明进行操作时，很快就可以编写" Hello World"程序。当您了解更多关于Python的知识时，您可能会着迷于它使用不同方

xiesheng 2020-08-06

盘点 Python 10 大常用数据结构（下篇）

上篇文章中4种数据结构相信大家都已经比较熟悉，因此我言简意赅的介绍一遍。接下来再详细的介绍下面6种数据结构及各自使用场景，会列举更多的例子。基本用法 deque 双端队列，基于list优化了列表两端的增删数据操作。实现原理：cpython实现deque使用

KAIrving 2020-08-02

盘点 Python 10 大常用数据结构（上篇）

如果你还处于Python入门阶段，通常只需掌握list、tuple、set、dict这类数据结构，做到灵活使用即可。因为相比于list, tuple实例更加节省内存，这点尤其重要。并且set内允许增删元素，且效率很高。但是值得注意，dict占用字节数是li

xiesheng 2020-08-02

图解！24张图彻底弄懂九大常见数据结构！ 原创 Amazing10 业余码农 5月24日

数据结构想必大家都不会陌生，对于一个成熟的程序员而言，熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合，特殊的结构在不同的应用场景中往往会带来不一样的处理效率。常用的数据结构可根据数据访问的特点分为线性结

范范 2020-07-30

什么是hash?

这个特定的算法就叫hash算法，hash算法并不是一个固定不变的算法。只要是能达到这个目的的算法都可以说hash算法。例如MD5,SHA，String.hashcode()都是hash算法。另外不同的输入可能会得出相同的hash值，那么这种现象称为hash

chenfei0 2020-07-30

数据结构--二叉树（Java）

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！能提高数据存储，读取的效率, 比如利用 二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。如果该二叉树的所有叶子节

waitwolf 2020-07-30
妖怪哪里跑

妖怪哪里跑

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号