顺序栈和链栈（算法设计和实验） |
您所在的位置：网站首页 › 栈空和栈满 › 顺序栈和链栈（算法设计和实验） |
顺序栈和链栈（算法设计和实验）
|
1. (算法设计题)
将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长(如下图所示)。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数，双栈数据结构定义如下： typedef struct { int top[2], bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数 }DblStack;
回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，但”good”不是回文，试写一算法利用栈判定给定的字符序列是否为回文。（提示：将一半字符入栈） #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } Stack; int IsEmpty(Stack *S) { return S->top == -1; } void Push(Stack *S, char c) { if (S->top == MAX_SIZE - 1) { printf("栈满\n"); exit(1); } S->data[++S->top] = c; } // 出栈 char Pop(Stack *S) { if (IsEmpty(S)) { printf("栈空!\n"); exit(1); } return S->data[S->top--]; } int Ishuiwen(char *str) { Stack S; int len = strlen(str); int i S->top = -1; // 将一半字符入栈 for (i = 0; i < len / 2; i++) { Push(&S, str[i]); } // 如果字符串长度为奇数，跳过中间字符 if (len % 2 != 0) { i++; } // 出栈并与剩余字符比较 while (str[i] != '\0') { if (str[i] != Pop(&S)) { return 0; // 不是回文 } i++; } return 1; // 是回文 } int main() { char str[MAX_SIZE]; scanf("%s", str); if (Ishuiwen(str)) { printf("是回文.\n"); } else { printf("不是回文.\n"); } return 0; } 初始化一个栈 Stack S 和一个索引 i。 将给定字符串的一半字符依次入栈，入栈过程中索引 i 逐步增加。 如果字符串的长度为奇数，则中间字符不需要入栈。 然后，从字符串的中间位置开始向后遍历，与栈中的字符依次比较。 如果栈中的字符与字符串中对应位置的字符不相同，则说明不是回文；否则继续比较。 如果字符串遍历完毕且栈为空，则说明给定的字符序列是回文；否则不是回文。 这个算法的时间复杂度取决于字符串长度的一半，因为它只遍历了一半的字符。因此，时间复杂度为 O(n/2)，其中 n 为字符串的长度。而空间复杂度为 O(n/2)，因为需要额外存储一半的字符在栈中。 附 录 顺序栈 #include #include #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef struct Sqstack { int* base; int top; }Sqstack; int initStack(Sqstack& s) { s.base = (int*)malloc(MAXSIZE * sizeof(int)); if (s.base == NULL) { return OVERFLOW; } s.top = 0; return OK; } int StackEmpty(Sqstack s) { if (s.top = 0) { return 1; } else { return 0; } } int GetLength(Sqstack s) { return s.top; } int ClearStack(Sqstack& s) { s.top = 0; return OK; } int DestroyStack(Sqstack& s) { if (s.base) { free(s.base); s.base = NULL; s.top = 0; } return OK; } int Push(Sqstack& s, int e) { if (s.top == MAXSIZE) { return ERROR; } s.base[s.top] = e; s.top++; return OK; } int Pop(Sqstack& s, int& e) { if (s.top == 0) { return ERROR; } s.top--; e = s.base[s.top]; return OK; } void printStack(Sqstack s) { int i = 0; while (i < s.top) { printf("%5d", s.base[i]); i++; } printf("\n"); } int GetTop(Sqstack s, int& e) { if (s.top == 0) { return ERROR; } e = s.base[s.top - 1]; return OK; } int main() { Sqstack s; if (initStack(s) == OK) { printf("初始化栈成功\n"); } else { printf("初始化栈失败\n"); } printf("请输入要入栈元素的个数\n"); int number = 0; int value; scanf("%d", &number); for (int i = 1;i next; } return count; } int StackEmpty(LinkStack s) { if (s == NULL) { return 1; } else { return 0; } } void printStack(LinkStack s) { StackNode* p = s; while (p) { printf("%5d", p->data); p = p->next; } printf("\n"); } int Push(LinkStack& s, int e) { StackNode* p = (StackNode*)malloc(sizeof(StackNode)); if (p) { p->data = e; p->next = s; s = p; return OK; } return ERROR; } int Pop(LinkStack& s, int e) { StackNode* p = s; if(s){ s = s->next; e = p->data; free(p); return OK; } else { return ERROR; } } int DestroyStack(LinkStack& s) { StackNode* p = s; while (p) { s = s->next; free(p); p = s; } s = NULL; return OK; } int Gettop(LinkStack s, int &e) { if (s) { e = s->data; return OK; } else { return ERROR; } } int main() { LinkStack s= NULL; printf("请输入要入栈的元素个数:\n"); int number = 0; scanf("%d", &number); int value = 0; for (int i = 1;i data; 这行代码将栈顶元素的值赋给了参数 e，因此 e 将被修改为栈顶元素的值。 在调用这个函数时，你需要传递一个整型变量的引用作为第二个参数，函数将会修改这个参数的值为栈顶元素的值。例如： int value; if (Gettop(s, value) == OK) { printf("成功获取栈顶元素\n"); printf("栈顶元素为:%d\n", value); } 在这个例子中，如果 Gettop 函数执行成功，value 将会被修改为栈顶元素的值，并在后续代码中使用。 |
【本文地址】