|
|
|---|---|
|
|
|
|
|
5.1 程序蜗居——内存
在C语言中，一般把内存分为5个区域，分别为全局区、代码区、常量区，以及堆、栈。其中， 全局区：存放在这个区域的数据，在整个程序的运行期间都是有效的，也就是生存期贯穿整个程序运行期。所以，全局区用以存放全局变量、静态变量。全局区的分配、释放均由编译器自动完成。 代码区：存放程序的区域。 常量区：编程的时候，经常会用到大量常量，这些常量在程序运行期间不会改变，这类数据就存放在常量区。常量区的分配、释放也是由编译器自动完成。 堆：程序运行期间，可能临时产生大量有用的数据，但这些数据只是临时的，并不需要程序持续保留，这个时候就需要临时分配一些内存空间来保存。当这些数据不再使用时，就没有再保留他们的必要了，弃之即可。而内存大小是有限的，不能随意丢弃不管。所以，不再保留这些数据时，还得收回分配的内存空间。这就是内存的动态分配和释放的原因。整个这些操作就是在所谓的堆区进行的。 栈：在没有操作系统的C语言编程中，除了main函数，都是可以被调用的函数。在被调函数中，由函数本身、且只供函数本身使用的变量，称为局部变量。这类数据存放在栈区。类似的数据还有调用函数时的形参等。 5.1.1 铁打的营盘流水的兵——动态内存分配 分配内存的函数有多个不同的原型，这些都已经集成在库函数stdlib.h中了。 1、函数一 void *malloc(unsigned int num_bytes); 调用该函数，需要用户指定分配内存空间的大小。分配成功后，系统为用户分配一块大小为num_bytes字节的内存空间。该函数的返回一个指向分配的这块内存的void型指针。在使用时，需要把改指针强制转换成需要的类型。若分配失败，则返回值为NULL。malloc函数只分配内存，并不进行初始化。 2、函数二 void *calloc(unsigned num, unsigned size); 调用该函数，同样需要用户指定相应的参数。参数包括元素的数量和每个元素的字节数。若分配成功，分配所得的内存空间大小为num*size字节，并且内存空间被初始化为0或NULL。函数返回值同样为指向这块内存的指针。若分配失败，则返回值为NULL。 3、函数三 void *realloc(void *ptr, size_t size); 调用该函数，对已有的内存空间进行重新分配。void类型的指针ptr指向已有的内存空间，size用来指定重新分配之后所得的整个空间大小。若分配成功，返回指向新分配空间的指针；如果分配失败，同样返回NULL。 5.1.2 可持续发展——内存的释放 内存释放的函数原型为： void free(void &*ptr); 动态分配的内存使用结束后，要及时释放。调用该函数，指向需要释放的内存空间地址，即可完成释放。 需要注意的是，内存释放，只是把这块内存的数据变成无效数据，而指针ptr依然指向这块内存。因此，释放内存后，要及时把指针指向NULL。 5.2 再说队列 队列，是一种数据结构。规定队列只能从一端插入，另一端删除。也就是先进队的数据先出队，后进的数据后出，即所谓的先进先出。 5.2.1 有头有尾的队列 有头有尾的队列，又称为单向队列。分别用front和rear指向队头、队尾。 front | 出队<--- data1 | data2 | data3 | | <---进队 | rear 队列的基本操作有队列初始化、入队、出队、判队空和判队满等。 其中需要说明的是，当front并没有指向队列的第一个位置，但rear却指向队列的最后一个位置。此时，队列前方有空间，但是队尾却无法再继续插入，这种现象称之为“假溢出”。 举个例子说明一下。
#include <stdio.h>
#define QUEUESIZE 10
int out = 0;
typedef struct
{
int front;
int rear;
int data[QUEUESIZE];
} QUEUE;
//入队
QUEUE InsertQueue(int data, QUEUE queue)
{
if(queue.rear < QUEUESIZE)
{
queue.data[queue.rear] = data;
queue.rear++;
}
else
printf("队列已满。\n");
return queue;
}
//出队
QUEUE OutQueue(QUEUE queue)
{
if(queue.front != queue.rear)
{
out = queue.data[queue.front];
queue.front++;
}
else
printf("队列为空。\n");
return queue;
}
int main()
{
QUEUE queue;
int i;
//初始化队列
queue.front = queue.rear = 0;
for(i = 100; i < 110; i++)
queue = InsertQueue(i, queue);
for(i = 0; i < 10; i++)
{
queue = OutQueue(queue);
printf("%d ", out);
}
getchar();
return 0;
}
5.2.2 无头无尾的循环队列 循环队列，是把队头、队尾相连，形成一个逻辑环。还是举例子来说明吧。
#include <stdio.h>
#define QUEUESIZE 10
int out = 0;
typedef struct
{
int front;
int rear;
int counter; //记录队列中元素的个数
int data[QUEUESIZE];
} CIRCLEQUEUE;
//判断队列为空
int IsQueueEmpty(CIRCLEQUEUE CircleQueue)
{
return CircleQueue.counter == 0;
}
//判断队列已满
int IsQueueFull(CIRCLEQUEUE CircleQueue)
{
return CircleQueue.counter == QUEUESIZE;
}
//入队
CIRCLEQUEUE InsertQueue(int data, CIRCLEQUEUE CircleQueue)
{
if(IsQueueFull(CircleQueue))
printf("队列已满。\n");
else
{
CircleQueue.data[CircleQueue.rear] = data;
CircleQueue.counter++;
CircleQueue.rear = (CircleQueue.rear + 1) % QUEUESIZE;
}
return CircleQueue;
}
//出队
CIRCLEQUEUE OutQueue(CIRCLEQUEUE CircleQueue)
{
if(IsQueueEmpty(CircleQueue))
printf("队列为空。\n");
else
{
out = CircleQueue.data[CircleQueue.front];
CircleQueue.counter--;
CircleQueue.front = (CircleQueue.front + 1) % QUEUESIZE;
}
return CircleQueue;
}
int main()
{
CIRCLEQUEUE CircleQueue;
int i;
//初始化循环队列
CircleQueue.front = 0;
CircleQueue.rear = 0;
CircleQueue.counter = 0;
for(i = 100; i < 110; i++)
CircleQueue = InsertQueue(i, CircleQueue);
for(i = 0; i < 10; i++)
{
CircleQueue = OutQueue(CircleQueue);
printf("%d ", out);
}
getchar();
return 0;
}
5.2.3 链式队列 链式队列，就是用链式结构存储的队列。链队介于单链表，其操作类似于链表的操作，只是在单链表上融合了队列的特性。依然举例说明。
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkNode_t
{
int data;
struct LinkNode_t *next;
} LINKNODE;
typedef struct LinkPoint_t
{
struct LinkNode_t *front;
struct LinkNode_t *rear;
} LINKQUEUE;
LINKNODE *pNode;
int out = 0;
//入队
LINKQUEUE* InsertQueue(int data, LINKQUEUE *pQueue)
{
pNode = (LINKNODE*)malloc(sizeof(LINKNODE));
pNode->data = data;
pNode->next = pQueue->rear->next;
pQueue->rear->next = pNode;
pQueue->rear = pNode;
return pQueue;
}
//出队
LINKQUEUE* OutQueue(LINKQUEUE *pQueue)
{
if(pQueue->front != pQueue->rear)
{
pNode = pQueue->front->next;
pQueue->front->next = pNode->next;
out = pNode->data;
if(pNode == pQueue->rear)
pQueue->rear = pQueue->front;
free(pNode);
}
return pQueue;
}
int main()
{
LINKQUEUE *pQueue;
int i;
//链队列初始化
pNode = (LINKNODE*)malloc(sizeof(LINKNODE));
pQueue = (LINKQUEUE*)malloc(sizeof(LINKQUEUE));
pNode->next = NULL;
pQueue->front = pQueue->rear = pNode;
for(i = 100; i < 110; i++)
pQueue = InsertQueue(i, pQueue);
for(i = 0; i < 10; i++)
{
pQueue = OutQueue(pQueue);
printf("%d ", out);
}
getchar();
return 0;
}
5.3 永恒的话题——堆栈 这里所说的堆栈，是一种数据结构，并非内存中的堆、栈。 5.3.1 特殊线性表之堆栈 堆栈限定了操作的位置，他只能从一端进行操作。能够操作的这一端为栈顶，另一端为栈底。也就是后进队的数据先出队，先进的数据后出，即所谓的后进先出。 5.3.2 堆栈的存储结构 堆栈分为顺序栈（顺序存储的堆栈）和链栈（链式存储的堆栈）两种。
#include <stdio.h>
#define STACKSIZE 10
typedef struct
{
int top;
int data[STACKSIZE];
} STACK;
int out = 0;
//进栈
STACK InsertStack(int data, STACK stack)
{
if(stack.top < STACKSIZE)
{
stack.data[stack.top] = data;
stack.top++;
}
else
{
printf("栈满。\n");
}
return stack;
}
//出栈
STACK OutStack(STACK stack)
{
if(stack.top > 0)
{
stack.top--;
out = stack.data[stack.top];
}
else
{
printf("栈空。\n");
}
return stack;
}
int main()
{
STACK stack;
int i;
//栈的初始化
stack.top = 0;
for(i = 100; i < 110; i++)
stack = InsertStack(i, stack);
for(i = 0; i < 10; i++)
{
stack = OutStack(stack);
printf("%d ", out);
}
getchar();
return 0;
}
5.4 顺藤摸瓜——链表 链式存储的线性表，简称链表。链表由多个链表元素组成，这些元素称为结点。结点之间通过逻辑连接，形成链式存储。存储结点的内存单元，可以是连续的，也可以是不连续的。链表的节点包含两个域，分别是值域、链域。值域用以存放节点值，链域用来存放下一个节点的地址或位置。 5.4.1 链表种种 链表，根据不同的角度，可以分为多种不同的类型。 从内存角度出发，可以分为静态链表、动态链表。从链表存储方式角度出发，可以分为单链表、双链表，和循环链表等。 5.4.2 寻根问祖——链表的建立 5.4.3 链表的操作 以循环链表为例，拿程序说明一下。
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkNode
{
int data;
struct LinkNode *next;
} *LIST;
//插入链表
LIST InsertList(int data, LIST pList)
{
LIST pLinkNode;
pLinkNode = (LIST)malloc(sizeof(LIST));
if(pLinkNode)
{
pLinkNode->data = data;
pLinkNode->next = pList->next;
pList->next = pLinkNode;
pList = pLinkNode;
}
else
printf("插入链表失败\n");
return pList;
}
//删除链表
LIST DeleteList(LIST pList)
{
LIST pLinkNode;
pLinkNode = (LIST)malloc(sizeof(LIST));
if(pLinkNode)
{
pLinkNode = pList->next;
pList->next = pLinkNode->next;
}
else
printf("删除链表失败\n");
return pList;
}
int main()
{
//初始化链表
LIST pList;
int i;
pList = (LIST)malloc(sizeof(LIST));
if(pList)
pList->next = pList;
else
printf("初始化链表失败\n");
for(i = 100; i < 110; i++)
pList = InsertList(i, pList);
for(i = 0; i < 10; i++)
pList = DeleteList(pList);
return 0;
}
5.5 C世界的树 5.5.1 C世界的树是这样的 5.5.2 “丫”形的二叉树 5.5.3 今天，你“栽树”了吗——二叉树的创建 5.5.4 一个也不能少——二叉树的遍历 直接拿程序说明一下。
#include <stdio.h>
#include <stdlib.h>
typedef struct tree_node
{
char data;
struct tree_node *lchild, *rchild;
} BT_Node;
BT_Node *CreateBTree(BT_Node *pTree)
{
char ch;
ch = getchar();
if(ch == '*')
pTree = NULL;
else
{
pTree = (BT_Node*)malloc(sizeof(BT_Node));
pTree->data = ch;
pTree->lchild = CreateBTree(pTree->lchild);
pTree->rchild = CreateBTree(pTree->rchild);
}
return(pTree);
}
void VisitNode(BT_Node *pTree)
{
printf(" %c\t", pTree->data);
}
void PreOrder(BT_Node *pTree)
{
if(pTree)
{
VisitNode(pTree);
PreOrder(pTree->lchild);
PreOrder(pTree->rchild);
}
else
return;
}
void MidOrder(BT_Node *pTree)
{
if(pTree)
{
MidOrder(pTree->lchild);
VisitNode(pTree);
MidOrder(pTree->rchild);
}
else
return;
}
void AfterOrder(BT_Node *pTree)
{
if(pTree)
{
AfterOrder(pTree->lchild);
AfterOrder(pTree->rchild);
VisitNode(pTree);
}
else
return;
}
int main()
{
BT_Node *pTree;
printf("输入树节点：\n");
pTree = (BT_Node*)malloc(sizeof(BT_Node));
pTree = CreateBTree(pTree);
if(pTree)
{
printf("前序排列：\n");
PreOrder(pTree);
printf("\n");
printf("中序排列：\n");
MidOrder(pTree);
printf("\n");
printf("后序排列：\n");
AfterOrder(pTree);
printf("\n");
}
return 0;
}
输入“abd**e*hj***cf**g**”。 二叉树示意图： 
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这个，没看懂。。。
|
