我写的一个堆实现大家帮看看有没BUG

ccqiji · 发表于 2012-1-8 11:17:55

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

老师布置的作业写个可以变长存字符串的程序要求缓存占最大使用率跟堆差不多

/*********************************************************
* 此程序非动态生成字符串空间 *
* 要想获得更大空间请修改三个宏 *
* 此程序不能指定位置添加数据. *
* 此程序添加的数据需要键入s命令排序,非自动 *
*********************************************************/
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_STR 10
#define STR_LEN 101
#define MAX_SIZE 1010
char szBuffer[MAX_SIZE];
int iStateTable[MAX_STR][4] = {0};
int (*piStateTable)[4] = iStateTable;
char *pSzArray[MAX_STR] = {NULL};
int iApplyCount = 0;
int iNeedSpace = 0;
int iSaveSpace = 0;
void UpdateSz(char *[], int *, int);
void SortSz(char *[], int );
void PrintSz(char *[], int );
int AddSz(char *[], int *);
int FoundSz(char *[], int , char *);
int ReadLine(char *, int n);
char *DeleteSz(char *[], int *, int);
void MakeEmptySz(char *[], int *);
void UpdateSz(char *[], int *, int);
int main(int argc, char* argv[])
{
int iCount = 0;
int i = 0;
int iFlag = 0;
for(;;)
{
printf("*************************输入命令****************************\r\n");
printf("*****<i>:添加数据 <s>:排序 <p>:显示数据 <f>:查找数据***** \r\n");
printf("*****<d>:删除数据 <x>:清空数据 <u>:更新数据 <q>:退出*********\r\n");
printf("*************************************************************\r\n");
printf(">");
iFlag = 0;
char cCmd;
fflush(stdin);
cCmd = getchar();
int iIsFound = 0;
int iDeleTeIndex = 0;
int iUpteIndex = 0;
switch(tolower(cCmd))
{
case 'u':
printf("输入要更新的数据:\r\n");
PrintSz(pSzArray, iCount);
if(iCount <= 0)
{
break;
}
printf("序号: ");
scanf("%d", &iUpteIndex);
if(iUpteIndex >= 1 && iUpteIndex <= iCount)
{
UpdateSz(pSzArray, &iCount, iUpteIndex);
printf("更新完成, 当前数据为:\r\n");
PrintSz(pSzArray, iCount);
}
else
{
printf("你输入了错误的序号\r\n");
}
break;
case 'i':
AddSz(pSzArray, &iCount); //添加数据
break;
case 's':
SortSz(pSzArray, iCount); //排序
break;
case 'p':
PrintSz(pSzArray, iCount); //显示数据
break;
case 'f':
iFlag = 1;
printf("输入要查找的数据:\r\n");
char szFound[STR_LEN];
ReadLine(szFound, STR_LEN);
iIsFound = FoundSz(pSzArray, iCount, szFound); //查找数据
if(iIsFound)
{
printf("找到了数据,第%d个,内容为:%s\r\n\r\n", iIsFound, szFound);
}
else
{
printf("没找到\r\n");
}
break;
case 'd':
printf("输入要删除第几个数据:\r\n");
PrintSz(pSzArray, iCount);
if(iCount <= 0)
{
break;
}
printf("序号: ");
scanf("%d", &iDeleTeIndex);
if(iDeleTeIndex >= 1 && iDeleTeIndex <= iCount)
{
printf("你删除了第%d个数据,内容为:%s\r\n", iDeleTeIndex, DeleteSz(pSzArray, &iCount, iDeleTeIndex));
}
else
{
printf("你输入了错误的序号\r\n");
}
break;
case 'x':
MakeEmptySz(pSzArray, &iCount); //清空数据
printf("清空数据成功\r\n");
break;
case 'q':
printf("统计:\r\n");
printf("你一共申请了%d次空间\r\n", iApplyCount);
printf("使用了%d字节空间\r\n", iNeedSpace - iSaveSpace);
printf("节约了%d字节空间\r\n", iSaveSpace);
system("pause");
return 0;
break;
default:
printf("你输入了神秘指令\r\n");
break;
}
}
return 0;
}
int ReadLine(char str[], int n)
{
int ch, i = 0;
fflush(stdin);
while (isspace(ch = getchar())) //忽略用户输入数据前面空格回车
{
}
while(ch != '\n')
{
if(i < n)
{
str[i++] = ch;
}
ch = getchar();
}
str[i] = '\0';
return i;
}
void SortSz(char *pSzArray[], int count)
{
int i;
int j;
int iMinOffset = 0;
char *temp;
for(i = 0; i < count; i++)
{
iMinOffset = i;
for(j = i + 1; j < count; j++)
{
if (strcmp(pSzArray[iMinOffset], pSzArray[j]) > 0) /*记录最小字符串的坐标*/
{
iMinOffset = j;
}
}
temp = pSzArray[i]; /*每次最小放最左边*/
pSzArray[i] = pSzArray[iMinOffset];
pSzArray[iMinOffset] = temp;
}
printf("排序完成\r\n");
}
void PrintSz(char *pSz[], int count)
{
int i;
if (count == 0)
{
printf("没有数据,请先添加\r\n");
return;
}
else
{
printf("数据为:\n");
for(i = 0; i < count; i++)
{
printf("%-2d: %s\n", i + 1, pSz[i]);
}
}
}
int AddSz(char *pSzArray[], int *count)
{
int i = 0;
char szTemp[STR_LEN];
printf("字符串排序最大支持长度为%d,最多%d个字符串输入exit退出输入\r\n", STR_LEN - 1, MAX_STR);
for(;;)
{
int iFlag = 0;
if(*count == MAX_STR)
{
printf("最大%d个字符串\r\n", *count);
break;
}
printf("输入第%d个字符串: ", *count + 1);
ReadLine(szTemp, STR_LEN - 1);
if(strcmp(szTemp,"EXIT") == 0 || strcmp(szTemp,"exit") == 0)
{
break;
}
int szLen = strlen(szTemp) + 1;
int iTableCount = piStateTable - iStateTable;
int iLeftBufferLen = 0;
int j = 0;
for(i = j; i < iTableCount; i++) //从第一个table开始找位置
{
iLeftBufferLen = 0;
j = i;
while(iStateTable[j][3] == 0)
{
iLeftBufferLen += iStateTable[j][2];
if (iLeftBufferLen >= szLen)
{
strcpy(szBuffer + iStateTable[i][1], szTemp); //拷贝到缓冲区;
pSzArray[*count] = szBuffer + iStateTable[i][1]; //指针指向缓冲区;
iStateTable[i][3] = 1; //置为忙
iStateTable[i][2] = szLen; //长度
iNeedSpace += szLen;
iApplyCount++;
iSaveSpace += szLen;
iStateTable[i][0] = iApplyCount;
j = i + 1;
while(iStateTable[j][1] < iStateTable[j + 1][1]) //更新后面表格偏移和长度问题
{
iStateTable[j][1] = iStateTable[j - 1][1] + iStateTable[j - 1][2];
if(iStateTable[j][1] > iStateTable[j + 1][1])
{
iStateTable[j][2]= 0;
}
else
{
iStateTable[j][2] = iStateTable[j + 1][1] - iStateTable[j][1];
}
j++;
}
iStateTable[j][1] = iStateTable[j - 1][1] + iStateTable[j - 1][2];
iFlag = 1;
(*count)++;
break;
}
j++;
if(j >= iTableCount)
{
break;
}
}
if (iFlag == 1)
{
break;
}
}
if(iFlag == 0)
{
int offset;
if(*count == 0)
{
offset = 0;
}
else
{
offset = piStateTable[-1][1] + piStateTable[-1][2];
}
strcpy(szBuffer + offset , szTemp);
pSzArray[*count] = szBuffer + offset; //指向字符串地址
iApplyCount++;
(*piStateTable)[0] = iApplyCount; //第几个数据
(*piStateTable)[1] = offset; //距表格偏移
(*piStateTable)[2]= strlen(szTemp) + 1; //长度
iNeedSpace += strlen(szTemp) + 1;
(*piStateTable)[3] = 1; //是否空闲
piStateTable++;
(*count)++;
}
}
return *count;
}
/**********************************************************
* 用于查找指定字符串 *
* 参数1.指向字符串指针的数组 *
* 参数2.指向字符串指针的个数 *
* 参数3.指向要查找的字符串 *
*********************************************************/
int FoundSz(char *pSzArray[], int count, char *pSz)
{
int i = 0;
for(i = 0; i < count; i++)
{
if(strcmp(pSzArray[i], pSz) == 0)
{
return i + 1;
}
}
return 0;
}
/**********************************************************
* 用于删除指定字符串 *
* 参数1.指向字符串指针的数组 *
* 参数2.指向字符串指针的个数 *
* 参数3.指向要删除的字符串 *
*********************************************************/
char *DeleteSz(char *pSzArray[], int *count, int iDeleteIndex)
{
int i = 0;
char *szReTemp = pSzArray[iDeleteIndex - 1];
iSaveSpace += strlen(pSzArray[iDeleteIndex - 1]) + 1;
for(i = 0; i <= piStateTable - iStateTable ; i++)
{
char *temp = szBuffer + iStateTable[i][1];
if (strcmp(pSzArray[iDeleteIndex - 1], temp) == 0)
{
break;
}
}
iStateTable[i][3] = 0;
for(i = iDeleteIndex - 1; i < *count; i++) //往左移
{
pSzArray[i] = pSzArray[i + 1];
}
pSzArray[*count] = NULL; //多出指针填空
(*count)--;
return szReTemp;
}
void MakeEmptySz(char *pSzArray[], int *count)
{
int i = 0, j = 0;
for(i = 0; i < *count; i++)
{
pSzArray[i] = NULL; //指针指向空
}
for(i = 0; i <= piStateTable - iStateTable; i++)
{
for(j = 1; j < 4; j++)
{
iStateTable[i][j] = 0; // 全部置0重新分配;
}
}
piStateTable = iStateTable;
*count = 0;
iSaveSpace += iNeedSpace - iSaveSpace;
}
void UpdateSz(char *pSzArray[], int *count, int iUpdateIndex)
{
DeleteSz(pSzArray, count, iUpdateIndex);
printf("更新为:\r\n");
char szUpdate[MAX_STR];
ReadLine(szUpdate, MAX_STR - 1);
int szLen = strlen(szUpdate) + 1;
int iTableCount = piStateTable - iStateTable;
int iLeftBufferLen = 0;
int j = 0;
int i = 0;
int iFlag = 0;
for(i = j; i < iTableCount; i++) //从第一个table开始找位置
{
iLeftBufferLen = 0;
j = i;
while(iStateTable[j][3] == 0)
{
iLeftBufferLen += iStateTable[j][2];
if (iLeftBufferLen >= szLen)
{
strcpy(szBuffer + iStateTable[i][1], szUpdate); //拷贝到缓冲区;
pSzArray[*count] = szBuffer + iStateTable[i][1]; //指针指向缓冲区;
iStateTable[i][3] = 1; //置为忙
iStateTable[i][2] = szLen; //长度
iNeedSpace += szLen;
iApplyCount++;
iSaveSpace += szLen;
iStateTable[i][0] = iApplyCount;
j = i + 1;
while(iStateTable[j][1] < iStateTable[j + 1][1])
{
iStateTable[j][1] = iStateTable[j - 1][1] + iStateTable[j - 1][2];
if(iStateTable[j][1] > iStateTable[j + 1][1])
{
iStateTable[j][2]= 0;
}
else
{
iStateTable[j][2] = iStateTable[j + 1][1] - iStateTable[j][1];
}
j++;
}
iStateTable[j][1] = iStateTable[j - 1][1] + iStateTable[j - 1][2];
iFlag = 1;
(*count)++;
break;
}
j++;
if(j >= iTableCount)
{
break;
}
}
if (iFlag == 1)
{
break;
}
}
if(iFlag == 0)
{
int offset;
if(*count == 0)
{
offset = 0;
}
else
{
offset = piStateTable[-1][1] + piStateTable[-1][2];
}
strcpy(szBuffer + offset , szUpdate);
pSzArray[*count] = szBuffer + offset; //指向字符串地址
iApplyCount++;
(*piStateTable)[0] = iApplyCount; //第几个数据
(*piStateTable)[1] = offset; //距表格偏移
(*piStateTable)[2]= strlen(szUpdate) + 1; //长度
iNeedSpace += strlen(szUpdate) + 1;
(*piStateTable)[3] = 1; //是否空闲
piStateTable++;
(*count)++;
}
char *szTemp = NULL;
szTemp = pSzArray[iUpdateIndex - 1];
pSzArray[iUpdateIndex - 1] = pSzArray[*count - 1];
pSzArray[*count - 1] = szTemp;
for(i = *count - 1; i > iUpdateIndex; i--)
{
szTemp = pSzArray[i];
pSzArray[i] = pSzArray[i - 1];
pSzArray[i - 1] = szTemp;
}
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 我写的一个堆实现 大家帮看看有没BUG

马上注册，结交更多好友，享用更多功能^_^

[技术交流] 我写的一个堆实现大家帮看看有没BUG