데이터 구조의 일부 코드

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("          
");
		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
",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
",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
",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
",i);
}
void Desplay(LinkList &L)
{
	LinkList p=L->next;
	while(p)
	{
		printf("       %d
",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("      
");
	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("            
");
	scanf("%d",&n);
	CreateList(L,n);
	printf("            
");
	scanf("%d",&n);
	CreateList(lb,n);
	MergeList(L,lb,lc);
	Desplay(lc);
	printf("       
");
	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
",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
",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");
}

창고
 
 

#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
",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  
",e);
}

void Pop(SqStack &S)
{
	if(S.top==S.base)
		exit(-1);
	int e=*--S.top;
	printf("  %d  
",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  
",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  
",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
");
	else
		printf("is not circle
");
	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;
}