目录
1.顺序表
顺序表的查找
顺序表的插入
顺序表的删除
顺序表有序插入
2.链表
带头结点单链表的查询
带头结点单链表的插入
带头结点单链表的删除
两个有序链表序列的合并
3.栈和队列
顺序栈的基本运算
循环队列出队入队(详细见博客http://t.csdn.cn/S8ep1)
循环队列入队出队 *** 作（详细见博客http://t.csdn.cn/mkfmL）
另类堆栈
十进制转二进制（顺序栈设计和应用）
进制转换
排队叫号系统
5.二叉树
求叶子结点个数
后缀表达式
哈夫曼编码
二叉树的遍历
统计二叉树结点个数
求二叉树的深度
6.图
图的创建（邻接矩阵）
图的创建-邻接表
1.顺序表 顺序表的查找
本题要求实现一个函数，要求从顺序表中查找指定元素，并返回第一个查找成功的元素在表中的位置序号，若查找失败，则返回0；
int LocateElem(SqList L,ElemType e)
{
for(int i = 0;i本题要求实现一个函数，在顺序表的第i个位置插入一个新的数据元素e，插入成功后顺序表的长度加1，函数返回值为1；插入失败函数返回值为0；
int ListInsert(SqList &L,int i,ElemType e)
{
if(L.length == MAXSIZE)
{
return 0;
}
if(i<1||i>L.length+1)
{
return 0;
}
int b = L.length;
for(;b>i-1;b--)
{
L.elem[b] = L.elem[b-1];
}
L.elem[b] = e;
L.length = L.length+1;
return 1;
}本题要求实现一个函数，要求将顺序表的第i个元素删掉，成功删除返回1，否则返回0；
int ListDelete(SqList &L,int i)
{
if(i>0&&i<=L.length)
{
int k = i-1;
for(i=k;i本题要求实现一个函数，要求将指定元素插入到有序表的合适位置，使得插入后仍然保持有序，若插入失败返回0；插入成功则返回1，并且顺序表的长度加1.
int SqInsert(SqList &L,ElemType e)
{
int i;
if(L.length==MAXSIZE)return 0;
for(i=L.length-1;i>=0;i--)
{
if(L.elem[i]>e)L.elem[i+1] = L.elem[i];
else break;
}
L.elem[i+1] = e;
L.length++;
return 1;
}
H为单链表的头指针，key为待查找的值（第一个为参考，第二个为准）
int Get_LinkList(LinkList H,ElemType key)
{
LinkList t;
int i;
t = H->next;
for(i=1;t!=NULL;i++)
{
if(t->data == key)
{
return i;
}
t = t->next;
}
if(t == NULL)
return 0;
}
ElementType FindKth( List L, int K )
{
int count = 1;
PtrToLNode p = L;
while(L!=NULL&&countNext;
count++;
}
if(p&&count==K)
return p->Data;
else
return ERROR;
} H为单链表的头指针，i为插入位置，e为新插入的值（第一个为参考，第二个为准）
Status ListInsert(LinkList &H,int i,ElemType e)
{
LinkList t,pi,n;
pi = (LinkList)malloc(sizeof(LNode));
int j = 1;
t = H->next;
n = H;
for(j = 1;j<=i;j++)
{
if(j==i)
{
pi->data = e;
pi->next = t;
n ->next = pi;
}
n = t;
t = t->next;
}
return OK;
}本题要求实现带头结点的单链表插入 *** 作，插入成功返回1，否则返回0。
int insert_link ( LinkList L,int i,ElemType e)
{
if(i<=0)return 0;
LinkList p = L;
LinkList pre = p;
int count = 1;
if(!L)return 0;
while(p)
{
pre = p;
p = p->next;
if(count == i)break;
if(p==NULL)break;
count++;
}
if(count!=i)return 0;//插入位置越界检查
LinkList pr = malloc(sizeof(struct LNode));
pr->data = e;
pre->next = pr;
pr->next = p;
return 1;
}H为单链表的头指针，i为删除位置（第一个为参考，第二个为准）
Status ListDelete(LinkList &H,int i)
{
LinkList t,n;
t = H->next;
n = H;
int j;
for(j=1;j<=i;j++)
{
if(j==i)
{
n->next = t->next;
}
n = t;
t = t->next;
}
}本题要求实现删除单链表的第i个元素结点，删除成功返回1，否则返回0。
int delete_link ( LinkList L,int i)
{
if(i<=0)return 0;
LinkList p = L;
int count = 1;
while(p&&countnext;
count++;
}
if(p->next == NULL)return 0;
LNode*pre = p->next;
p->next = pre->next;
free(pre);
return 1;
}
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
List Merge( List L1, List L2 ) {
List pa, pb, pc, L;
L = (List)malloc(sizeof(struct Node)); //申请一个头结点L.
pa = L1->Next; //指针pa指向L1的第一个结点。
pb = L2->Next; //指针pb指向L2的第一个结点。
pc = L; //指针pc指向上面创立的头结点L.
while ( pa && pb ) { //当L1和L2链表都没有遍历完成的时候。
if ( pa->Data <= pb->Data ) { //若pa结点的数据小。
pc->Next = pa; //把pa串入L中。
pc = pa; //pc移向当前最后一个结点pa，这也是尾插。
pa = pa->Next; //在L1链表中，更新pa位置。
} else {
pc->Next = pb;
pc = pb;
pb = pb->Next;
}
}
/*如果L1未遍历完，将L1全部串入L，如果L2未遍历完，将L2全部串入L*/
pc->Next = pa ? pa : pb;
L1->Next = NULL;
L2->Next = NULL;
return L;
}编写函数实现顺序栈的初始化、出栈、入栈运算。
Status iniStack(Sqstack&S)
{
S.base = (SElemType*)malloc(100*sizeof(SElemType));
S.top = S.base;
S.stacksize = 100;
}
Status push(Sqstack&S,SElemType x)
{
if(S.top - S.base >= S.stacksize)
return 0;
*S.top = x;
S.top++;
return 1;
}
Status pop(Sqstack&S,SElemType &e)
{
if(S.base == S.top)
return 0;
S.top--;
e =*S.top;
return 1;
}用一个数组表示循环队列，请编写算法实现循环队列的初始化、入队和出队 *** 作。
void InitQ(SqQueue &Q,int N)
{
Q.base = (int*)malloc(N*sizeof(int));
Q.front = 0;
Q.rear = Q.front;
}
void AddQ(SqQueue &Q,int x)
{
if((Q.rear+1)%N==Q.front)
{
printf("Queue Full\n");
}
else{
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%N;
}
}
Status DeleteQ(SqQueue &Q,int &e)
{
if(Q.rear == Q.front)
{
printf("Queue Empty\n");
return 0;
}
e = Q.base[Q.front];
Q.front = (Q.front+1)%N;
return 1;
}Status InitQueue(SqQueue& Q)
{
Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
if (!Q.base)
exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
Status EnQueue(SqQueue& Q, QElemType e) {
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue& Q, QElemType& e)
{
if (Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}在栈的顺序存储实现中，另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈 *** 作。如何判断堆栈为空或者满？
注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果队列是空的，则Pop函数必须输出“Stack Empty”，并且返回ERROR。
解题思路：
1、题目中说的上一个，是形式上的上一个，它脑袋顶上的一个而不是前一个。
2、审好题，在pop中如果有值返回的是数。其他的按常规处理，进栈先进后加，出栈先退到前一个再出栈。
bool Push(Stack S,ElementType X)
{
if(S->Top == S->MaxSize)
{
printf("Stack Full\n");
return false;
}
else
{
S->Data[S->Top++] = X;
return true;
}
}
ElementType Pop(Stack S)
{
if(S->Top == 0)
{
printf("Stack Empty\n");
return ERROR;
}
else
{
return S->Data[--S->Top];
}
}设计一个顺序栈，并利用该顺序栈将给定的十进制整整数转换为二进制并输出。
#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();
/* 元素x入栈 */
void Push(int x);
/* 取栈顶元素 */
int getTop();
/* 删除栈顶元素 */
void Pop();
bool Push( Stack S, ElementType X ){
if(S->Top==S->MaxSize){
printf("Stack Full\n");
return false;
}
else{
S->Data[S->Top++]=X;
return true;
}
}
ElementType Pop( Stack S ){
if(S->Top==0){
printf("Stack Empty\n");
return ERROR;
}
else{
return S->Data[--S->Top];
}
}
本题要求实现十进制转R（R<10 && R>0）进制。
接口参数解释：其中 S 为顺序栈， x 是入栈元素的值；n是要转换的十进制数，R则是要转换成的进制 ，e是出栈元素。函数类型Status代表状态，正确完成入栈运算返回OK，由于栈满无法正常入栈则返回OVERFLOW。
Status iniStack(Sqstack &S)
{
S.base = (int*)malloc(stack_INIT_SIZE*sizeof(SElemType));
if(!S.base)
return 0;
S.top = S.base;
S.stacksize = stack_INIT_SIZE;
return 1;
}
Status push(Sqstack &S,SElemType x)
{
if(!S.base)
return 0;
if(S.top - S.base >= S.stacksize)
{
S.base = (int*)realloc(S.base,(S.stacksize+ stackINCREMENT)*sizeof(SElemType));
if(!S.base)
return 0;
S.top = S.base + S.stacksize;
}
*S.top++ = x;
return 1;
}
Status pop(Sqstack &S,SElemType &e)
{
if(!S.base||S.top == S.base)
return 0;
e = *--S.top;
return 1;
}
void conversion(int n,int R)
{
Sqstack S;
iniStack(S);
SElemType e;
while(n)
{
push(S,n%R);
n /= R;
}
while(S.top!=S.base)
{
pop(S,e);
printf("%d",e);
}
}
编写程序实现银行排队叫号系统，采用链队列作为存储结构。
Status InitLinkQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
return 0;
Q.front->next = NULL;
return 1;
}
Status EnLinkQueue(LinkQueue &Q,QElemType e)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if(!p)
return 0;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return 1;
}
Status DeLinkQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front == Q.rear)
return 0;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return 1;
}
Status QueueEmpty(LinkQueue Q)
{
if(Q.front == Q.rear)
return 1;
else
return 0;
}
#include
using namespace std;
void creat(BiTree &T)//创建
{
char ch;
cin>>ch;
if(ch=='#')
{
T=NULL;
return;
}
else
{
T= (BiTree)malloc(sizeof(BiTNode));
T->data=ch;
creat(T->lchild);
creat(T->rchild);
}
}
int countleaf(BiTree T)
{
if (T==NULL) {
return 0;
}
if ((T->lchild == NULL)&& (T->rchild== NULL)) {
return 1;
}
else return countleaf(T->lchild)+ countleaf(T->rchild);
}
本题要求实现一个函数，输出二叉树表示的表达式的后缀式。
void Suffix(BiTree T)
{
if(T)
{
Suffix(T->lchild);
Suffix(T->rchild);
printf("%c ",T->data);
}
}
编写函数实现哈夫曼编码。输入结点个数(保证个数>1)及各结点的权值，为各结点进行编码。
其中 HT 为哈夫曼树，n 为叶子结点个数， HC 为哈夫曼编码。
void CreateHuffman_tree(HuffmanTree &HT,int n)
{
int m, s1, s2, i;
if (n <= 1)
return;
m = 2 * n - 1;
HT = new HTNode[m + 1]; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
for (i = 1; i <= m; ++i) //将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (i = 1; i <= n; ++i) //输入前n个单元中叶子结点的权值
scanf("%d",&HT[i].weight);
/*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/
for (i = n + 1; i <= m; ++i)
{ //通过n-1次的选择、删除、合并来创建赫夫曼树
Select(HT, i - 1, s1, s2);
//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
// 并返回它们在HT中的序号s1和s2
HT[s1].parent = i;
HT[s2].parent = i;
//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
HT[i].lchild = s1;
HT[i].rchild = s2; //s1,s2分别作为i的左右孩子
HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和
}
}
/*建立n个叶子结点的哈夫曼树*/
void Huffman_code(HuffmanTree HT,HuffmanCode &HC,int n)
{
char *cd;
cd=(char*)malloc((n+1)*sizeof(char));
int start,c,i,f;
HC=new char*[n+1];
cd[n-1]='G';
for(i=1;i<=n;++i)
{
start=n-1;
c=i;f=HT[i].parent;
while(f!=0)
{
--start;
if(HT[f].lchild==c) cd[start]='0';
else cd[start]='1';
c=f;f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
}//求哈夫曼编码
输入二叉树的先序遍历序列，以#代表空树，输出该二叉树的中序遍历序列。例如，有如下二叉树，其先序序列为：ABC##DE#G##F###，输出其中序序列：CBEGDFA
void creat(BiTree &Tree)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
Tree=NULL;
else
{
Tree=(BiTree)malloc(sizeof(BiTree));
Tree->data = ch;
creat(Tree->lchild);
creat(Tree->rchild);
}
}
void InOrder(BiTree Tree)
{
if(Tree)
{
InOrder(Tree->lchild);
printf("%c",Tree->data);
InOrder(Tree->rchild);
}
}int NodeCount ( BiTree T)
{
int nodes;
if(T==NULL)
return 0;
else
nodes = 1+NodeCount(T->lchild)+NodeCount(T->rchild);
return nodes;
}int Depth(BiTree T)
{
if(T==NULL)
return 0;
else
{
if(Depth(T->lchild)>Depth(T->rchild))
return Depth(T->lchild)+1;
else
return Depth(T->rchild)+1;
}
}本题要求建立一个无向图，采用邻接矩阵做为存储结构。v 为图，采用邻接矩阵存储结构，int locate(MGraph G,char v)
{
int temp=0;
for(temp=0;temp
int locate(ALGraph G,char v)
{
int i;
for(i=0;iadjvex=temp2;
e->nextarc=G.vertices[temp1].firstarc;
G.vertices[temp1].firstarc=e;
e=(ArcNode*)malloc(sizeof(ArcNode));
e->adjvex=temp1;
e->nextarc=G.vertices[temp2].firstarc;
G.vertices[temp2].firstarc=e;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）